Editorial for Bubble Cup V8 A Fibonotci


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's first solve a simpler problem – when the sequence c is cyclic, i.e. when ci=cimodN, for i0.

This simpler version is similar to Fibonacci sequence. Actually, for N=1 and c0=1, it is the Fibonacci sequence. To find the Kth number of these kinds of recursive sequences fast we should first write them in their matrix form. Matrix form of this sequence is:

(FiFi1)=(ci1ci210)(Fi1Fi2)

Expanding this, we can see that

(FKFK1)=CK1CK2C2C1(F1F0), where Ci=(cici110)

How do we calculate this efficiently?

For relatively small K, and we will take K<N for this case, we can do this just by multiplying all the matrices. For large K (KN), we will take advantage of the fact that c is cyclic. Since c is cyclic with cycle of length N, we know that CN1CN2C1C0=CiN+(N1)CiN+(N2)CiN+1CiN, for i0 (note that C0=(c0cN110)). Let's define this product of matrices as S=CN1CN2C1C0.

Now, we can write a formula for FK that can be calculated quickly:

(FKFK1)=Ca1Ca2C1C0SbCN1CN2C2C1(F1F0), where b=(KN)divN and a=KmodN

We can calculate Sb in O(logb) steps using exponentiation by squaring, and then we can just multiply everything in the expression to get FK quickly.

Let's get back to the full problem, when c is almost cyclic. In this case, we cannot just use Sb in the formula above, because some matrices in Sb may not respect the cyclic property. Instead of Sb, we will have something like

SSSE1SSSE2=St1E1St2E2St3

where Ei denotes the product of matrices of the cycle, with some matrices being different than the matrices of the original cycle. Also, i2M since each of the M values of c are different than values of the original cycle appears in exactly two matrices, so at most 2M of cycles are affected.

We can still calculate each Sti quickly, using exponentiation by squaring. Since there are at most 2M of those, total complexity of this would be O(MlogK).

Now we only need to calculate each Ei. Naive way would be to just multiply all matrices of Ei. Since the number of matrices is N, this would be O(NM) worst case, which is too slow. To quickly calculate Ei, we will initially create a segment tree of matrices, with matrices of original cycle in the leaves. Internal nodes of the tree will represent the product of their children. This means that the root will represent the product of all matrices in the cycle. To calculate Ei, we will just update our segment tree with those values that are different than the original values of the cycle. We will do this by updating the corresponding leaves of the tree, moving up to the root and updating the products in the internal nodes. After we're done updating the tree with all of the matrices that are different than matrices of the original cycle, we will just use the product in the root of the tree. Finally, we will update the tree back with matrices of the original cycle in order to reuse the segment tree for Ei+1.

Since there are O(N) nodes in the segment tree, the complexity of updating is O(logN). The total complexity is then O(MlogN+MlogK). We should also mention that the constant factor is not very small, since we operate on matrices and not just integers.

Note that we need to find FKmodP and P may not even be a prime number. However, this does not affect us since we only deal with operations of addition and multiplication throughout the whole procedure and we can just do them all modulo P.


Comments

There are no comments at the moment.