Test Data Generation
Contest: VK Cup 2017 - Round 3
Difficulty rating: 3400
Tags: combinatorics, divide and conquer, dp, fft, math, number theory

Test data generation is not an easy task! Often, generating big random test cases is not enough to ensure thorough testing of solutions for correctness.

For example, consider a problem from an old Codeforces round. Its input format looks roughly as follows:

The first line contains a single integer n (1 ≤ n ≤ maxn) — the size of the set. The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ maxa) — the elements of the set in increasing order.

If you don't pay attention to the problem solution, it looks fairly easy to generate a good test case for this problem. Let n = maxn, take random distinct ai from 1 to maxa, sort them... Soon you understand that it's not that easy.

Here is the actual problem solution. Let g be the greatest common divisor of a1, a2, ..., an. Let x = an / g - n. Then the correct solution outputs "Alice" if x is odd, and "Bob" if x is even.

Consider two wrong solutions to this problem which differ from the correct one only in the formula for calculating x.

The first wrong solution calculates x as x = an / g (without subtracting n).

The second wrong solution calculates x as x = an - n (without dividing by g).

A test case is interesting if it makes both wrong solutions output an incorrect answer.

Given maxn, maxa and q, find the number of interesting test cases satisfying the constraints, and output it modulo q.

Input format:
The only line contains three integers maxn, maxa and q (1 ≤ maxn ≤ 30 000; maxn ≤ maxa ≤ 109; 104 ≤ q ≤ 105 + 129).

Output format:
Output a single integer — the number of test cases which satisfy the constraints and make both wrong solutions output an incorrect answer, modulo q.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first example, interesting test cases look as follows:

Example input:
3 6 100000

Example output:
4

Example input:
6 21 100129

Example output:
154

Editorial:
This problem was inspired by division 1 problem A from Codeforces Round #201, which I tested: http://codeforces.com/contest/346/problem/A. Several hours before the round, I noticed that all test cases except for the examples were generated randomly. Moreover, there were three cases with maxn = 10 and maxa = 100, twenty cases with maxn = 100 and maxa = 109, and that's all. Not surprisingly, all test cases had even n and greatest common divisor equal to 1.
The problem statement tells us that interesting test cases have odd n, even an, and odd an / g. Suppose that g is divisible by 2k and not divisible by 2k + 1 for some k ≥ 1. Let's focus on interesting test cases with some fixed value of k.
We choose integers a1 < a2 < ... < an from 1 to maxa, all divisible by 2k, with an not divisible by 2k + 1. This is equivalent to choosing integers a1 < a2 < ... < an from 1 to $$b = \left\lfloor \frac{\max_a}{2^k} \right\rfloor$$ with an being odd.
Thus, for fixed k, the problem asks us to calculate the number of ways to choose at most maxn, but an odd number, of integers from 1 to b so that the largest chosen number is odd.
Let f(b, n, p) be the number of ways to choose exactly n integers from 1 to b so that the largest chosen number has parity p (we define f(b, 0, 0) = 1 and f(b, 0, 1) = 0). Suppose that for fixed b we have calculated the values of f(b, n, p) for all n ≤ maxn and $$p \in \{0, 1\}$$. Can we calculate all the values of f(2b, n, p) quickly? Yes, we can!
Here is a formula which allows us to do that:
The first summand corresponds to the case when out of integers from 1 to 2b, we only choose those from 1 to b. In the other case, we iterate over i — the number of integers chosen from 1 to b. It follows that we don't care about the parity of the largest of these i integers, but we have n - i integers chosen from b + 1 to 2b, and we know the number of ways to choose those with the largest integer of the required parity (which might change if b is odd).
This formula allows us to calculate all the values of f(2b, n, p) in O(maxn2), but we can still do better. Let xi = f(b, i, 0) + f(b, i, 1) and $$y_{j} = f(b,j,p \oplus (b \mod 2))$$. Then,
The right hand side is nothing else but the convolution of sequences x and y, so all these values can be calculated in $${ \mathcal { O } } \left( \max _ { n } \log \max _ { n } \right)$$ using Fast Fourier Transform. The modulo q given in the input was set to a low enough value so that doing FFT in doubles and rounding the result to the nearest integer gave enough precision. Discrete Fourier Transform with two different modulos can also be used, though it's several times slower.
It's also important that, given all the values of f(b, n, p), it's easy to calculate all the values of f(b + 1, n, p) in O(maxn) time. This means we can calculate the values of f(b, n, p) for any b in $$O\left(\max_{n}\log\max_{n}\log b\right)$$ using an idea similar to exponentiation by squaring.
Finally, recall that we need to find the values of f(b, n, p) for all $$b = \left\lfloor \frac{\max_a}{2^k} \right\rfloor$$, that is, for $$\log \max_a$$ different values of b. Doing calculations separately for all b gives a solution which works in $${\cal O}\left(\max_{n}\log\max_{n}\log^{2}\max_{a}\right)$$.
We can do better if we notice that while doing calculations for $$b = \left\lfloor \frac{\max_a}{2} \right\rfloor$$, we also do the calculations for all $$b = \left\lfloor \frac{\max_a}{2^k} \right\rfloor$$ naturally. Thus, we only need $$\log \max_a$$ convolutions. The final complexity of the solution is $${\cal O}\left(\max_{n}\log\max_{n}\log\max_{a}\right)$$.