Math, math everywhere
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 3200
Tags: brute force, dp, math, meet-in-the-middle, number theory

If you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string $$s = s_0 \ldots s_{m-1}$$ and an integer $$N = p_{1}^{\alpha_{1}} \ldots p_{n}^{\alpha_{n}}$$. Find the number of integers k, 0 ≤ k < N, such that for all i = 0, 1, ..., m - 1

$$\gcd(k+i,N)=1 \text{ if and only if } s_i=1$$

Input format:
In the first line of input there is a string s consisting of 0's and 1's (1 ≤ |s| ≤ 40).

In the next line of input there is an integer n (1 ≤ n ≤ 5·105).

Each of the next n lines contains two space-separated integers pi, αi (1 ≤ pi, αi ≤ 109, pi is prime). All pi are distinct.

Output format:
A single integer — the answer to the problem.

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

Example input:
1
2
2 1
3 1

Example output:
2

Example input:
01
2
3 2
5 1

Example output:
15

Editorial:
First I'll describe our original approach to this problem, and then some issues we encountered after the round finished.
Suppose that p1 = 2. If we have $$x \equiv 0 (\bmod 2)$$, then the string s must look like 0?0?0?..., that is, all even positions 0, 2, 4, ... will have 0's (for all others, we can't say), and if $$x \equiv 1 (\bmod 2)$$, then s looks like ?0?0?0.... Similarly, knowing the remainder of x modulo a prime p in factorization of N implies that there are zeros in s with p positions apart. If we fix all remainder modulo p1, ..., pn, then the string will be determined unambigiously. Notice that after fixing the modulos, there are still N' = p1α1 - 1... pnαn - 1 possible x's between 0 and N - 1; we will simply multiply the answer by N' in the end.
At this point we have a brute-force solution: try all values for remainders, count how many of the values give the string s. This is of course too slow, but we can make a few optimizations:
• Make a brute-force into a DP by introducing memoization. We will count the number of ways to obtain each partial string s after fixing first i remainders. Of course, we don't have to store all 2m masks, but just the reachable ones.
• Once pi > m, each choice of remainder either places a single zero into a string, or doesn't change anything. At this point we are not interested in the full mask, but rather in the number of "unsatisfied" zeros of initial string s. Each transition either satisfies one zero, or doesn't change anything; the number of transitions of each kind is easy to count.
We will do a full memoization DP for pi ≤ m, and continue with a compressed DP once pi > m. The second part can be done in O(nm) time and O(m) memory. The complexity of the first part depends on the total number of states in the memoization DP.
Turns out this number can be much larger than we anticipated on certain tests, for instance, primes starting from 5 or 7. On these cases, all our model solutions received time out. Such tests didn't appear in the original test set, of course.
[user:KAN] and myself tried to improve the solution. The idea behind our optimization is that once pi > m / 2, several central bits of the mask behave just like the "unsatisfied" bits in the large-prime part of the original solution: if we choose to cover them, it will be the single bit we cover. Thus we can do a "hybrid" DP that has parameters (number of unsatisfied bits in the middle, mask of all the rest bits).
[user:KAN]'s solution used "naive" mask DP for pi ≤ 23, switched to static array for pi = 29, 31, 37, and then proceeded to large primes as before. I tried to write a self-adaptive solution that handles all ranges of primes pretty much the same way. [user:KAN] was more successful: his solution works in $$\sim 3.5$$ seconds on all cases we could counstruct; my solution works in $$\sim 11$$ seconds and uses a lot of excess memory.
[user:KAN]'s solution: [submission:24707930], my solution: [submission:24707929].