## Editorial for DMOPC '18 Contest 2 P5 - Another Sequence Problem

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.

Authors: r3mark

For the first subtask, dynamic programming suffices. More specifically, let be the number of sequences with elements and sum to exactly . It is easy to see that . So transition can be done in .

Time Complexity:

For the second subtask, some math (e.g. generating functions, stars and bars) yields a closed form. It is well-known that the number of ways to add non-negative numbers to sum to is . So the final answer is going to be The is because is not in the set. Then by the hockey-stick identity, this sum becomes This can be easily calculated in .

Time Complexity:

For the third subtask, note that there are at most non-zero elements in the sequence. Using the dynamic programming solution from the first subtask, we can compute the number of sequences without using any 's using a certain number of terms in . Then with a little math, we can find the number of sequences which have a certain number of non-zero terms and the rest .

Time Complexity:

For the final subtask, we use the trick mentioned here. If is the number of sequences of length which sum to exactly and is the number of sequences of length which sum to exactly , then A similar formula can be found to calculate the number of sequences of length . So instead of checking all 's, only are necessary. Note that this is equivalent to exponentiation by squaring and is much more obvious if this problem is interpreted as a matrix multiplication problem or interpreted with its generating function.

Time Complexity:

• BaturaDima  commented on Oct. 12, 2018, 10:51 a.m.

Can you describe second task solution more concrete? And provide correct time compexety for it.

• r3mark  commented on Oct. 12, 2018, 4:10 p.m.

The derivation of the answer has been provided and the time complexity has been fixed. I treated the modular inverse operation as in the original time complexity.