Problem Statement
Magical Girls are girls who have magical powers. They fight against evil witches to protect the Earth. You, one of the Magical Girls, are now fighting against an evil witch. You want to use ultimate magic to defeat the witch. To use ultimate magic you have to chant a magical spell. The spell is determined with a sequence A. A is the sequence of strings which is determined with a sequence first. Each element of first is a string which contains only ‘0’ and ‘1’. Let K be the number of elements in first. Each element of A is defined as follows: for all i, \(0 <= i < K, A[i] = first[i]\). Otherwise, \(A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + ...\)(while i-m*K-1 is not less than 0). Here operator ‘+’ denotes concatenation of strings.
Tutorial
Again, the problem constraints gives a hint where the gap between the \(|right-left| <= 1000\). So then we can loop through the entire range starting from the left index and find the character at that position. The result keeps the count of the number of ‘1’ along that window. To find the character at the ith position, we use recursion and simulate the recurrence algorithm.
Code
class MagicalGirlLevelThreeDivTwo {
public:
long long lenk[110], K;
vector<string> f;
char go(int ith, long long idx) {
if (ith < K) {
return f[ith][idx];
} else {
int pth = ith - 1;
long before = 0;
while (idx >= before + lenk[pth]) {
before += lenk[pth];
pth -= K;
}
return go(pth, idx - before);
}
}
int theCount(vector<string> first, int n, long long lo, long long hi) {
memset(lenk, 0, sizeof(lenk));
for (int i = 0; i < first.size(); i++)
lenk[i] = first[i].size();
f = first;
K = first.size();
for (int k = K; k <= n; k++)
for (int e = k - 1; e >= 0; e -= K) {
lenk[k] += lenk[e];
lenk[k] = min(lenk[k], hi + 1);
}
int res = 0;
for (long long i = lo; i <= hi; i++)
res += (go(n, i) == '1' ? 1 : 0);
return res;
}
}