Number of different binary sequences of length n generated using exactly k flip operations

Question

Consider a binary sequence b of length N. Initially, all the bits are set to 0. We define a flip operation with 2 arguments, flip(L,R), such that:

• All bits with indices between L and R are "flipped", meaning a bit with value 1 becomes a bit with value 0 and vice-versa. More exactly, for all i in range [L,R]: b[i] = !b[i].
• Nothing happens to bits outside the specified range.

You are asked to determine the number of possible different sequences that can be obtained using exactly K flip operations modulo an arbitrary given number, let's call it MOD.
More specifically, each test contains on the first line a number T, the number of queries to be given. Then there are T queries, each one being of the form N, K, MOD with the meaning from above.

• 1 ≤ N, K ≤ 300 000
• T ≤ 250
• 2 ≤ MOD ≤ 1 000 000 007
• Sum of all N-s in a test is ≤ 600 000
• time limit: 2 seconds
• memory limit: 65536 kbytes

---

Example :
Input :
1
2 1 1000
Output :
3
Explanation :
There is a single query. The initial sequence is 00. We can do the following operations :
flip(1,1) ⇒ 10
flip(2,2) ⇒ 01
flip(1,2) ⇒ 11
So there are 3 possible sequences that can be generated using exactly 1 flip.

---

Some quick observations that I've made, although I'm not sure they are totally correct :
If K is big enough, that is if we have a big enough number of flips at our disposal, we should be able to obtain 2ⁿ sequences.
If K=1, then the result we're looking for is N(N+1)/2. It's also C(n,1)+C(n,2), where C is the binomial coefficient.
Currently trying a brute force approach to see if I can spot a rule of some kind. I think this is a sum of some binomial coefficients, but I'm not sure.
I've also come across a somewhat simpler variant of this problem, where the flip operation only flips a single specified bit. In that case, the result is C(n,k)+C(n,k-2)+C(n,k-4)+...+C(n,(1 or 0)). Of course, there's the special case where k > n, but it's not a huge difference. Anyway, it's pretty easy to understand why that happens.I guess it's worth noting.

Answer 1

Here are a few ideas:

1. We may assume that no flip operation occurs twice (otherwise, we can assume that it did not happen). It does affect the number of operations, but I'll talk about it later.

2. We may assume that no two segments intersect. Indeed, if L1 < L2 < R1 < R2, we can just do the (L1, L2 - 1) and (R1 + 1, R2) flips instead. The case when one segment is inside the other is handled similarly.

3. We may also assume that no two segments touch each other. Otherwise, we can glue them together and reduce the number of operations.

4. These observations give the following formula for the number of different sequences one can obtain by flipping exactly k segments without "redundant" flips: C(n + 1, 2 * k) (we choose 2 * k ends of segments. They are always different. The left end is exclusive).

5. If we had perform no more than K flips, the answer would be
   sum for k = 0...K of C(n + 1, 2 * k)

6. Intuitively, it seems that its possible to transform the sequence of no more than K flips into a sequence of exactly K flips (for instance, we can flip the same segment two more times and add 2 operations. We can also split a segment of more than two elements into two segments and add one operation).

7. By running the brute force search (I know that it's not a real proof, but looks correct combined with the observations mentioned above) that the answer this sum minus 1 if n or k is equal to 1 and exactly the sum otherwise.

That is, the result is C(n + 1, 0) + C(n + 1, 2) + ... + C(n + 1, 2 * K) - d, where d = 1 if n = 1 or k = 1 and 0 otherwise.

Here is code I used to look for patterns running a brute force search and to verify that the formula is correct for small n and k:

reachable = set()
was = set()


def other(c):
    """
    returns '1' if c == '0' and '0' otherwise
    """
    return '0' if c == '1' else '1'


def flipped(s, l, r):
    """
    Flips the [l, r] segment of the string s and returns the result
    """
    res = s[:l]
    for i in range(l, r + 1):
        res += other(s[i]) 
    res += s[r + 1:]
    return res


def go(xs, k):
    """
    Exhaustive search. was is used to speed up the search to avoid checking the
    same string with the same number of remaining operations twice.
    """ 
    p = (xs, k)
    if p in was:
        return
    was.add(p)
    if k == 0:
        reachable.add(xs)
        return
    for l in range(len(xs)):
        for r in range(l, len(xs)):
            go(flipped(xs, l, r), k - 1)


def calc_naive(n, k):
    """
    Counts the number of reachable sequences by running an exhaustive search
    """
    xs = '0' * n
    global reachable
    global was
    was = set()
    reachable = set()
    go(xs, k)
    return len(reachable)


def fact(n):
    return 1 if n == 0 else n * fact(n - 1)


def cnk(n, k):
    if k > n:
        return 0
    return fact(n) // fact(k) // fact(n - k)


def solve(n, k):
    """
    Uses the formula shown above to compute the answer
    """
    res = 0        
    for i in range(k + 1):
        res += cnk(n + 1, 2 * i)
    if k == 1 or n == 1:
        res -= 1
    return res


if __name__ == '__main__':
    # Checks that the formula gives the right answer for small values of n and k
    for n in range(1, 11):
        for k in range(1, 11):   
            assert calc_naive(n, k) == solve(n, k)

This solution is much better than the exhaustive search. For instance, it can run in O(N * K) time per test case if we compute the coefficients using Pascal's triangle. Unfortunately, it is not fast enough. I know how to solve it more efficiently for prime MOD (using Lucas' theorem), but O do not have a solution in general case.

Multiplicative modular inverses can't solve this problem immediately as k! or (n - k)! may not have an inverse modulo MOD.

Note: I assumed that C(n, m) is defined for all non-negative n and m and is equal to 0 if n < m.

I think I know how to solve it for an arbitrary MOD now.

1. Let's factorize the MOD into prime factors p1^a1 * p2^a2 * ... * pn^an. Now can solve this problem for each prime factor independently and combine the result using the Chinese remainder theorem.

2. Let's fix a prime p. Let's assume that p^a|MOD (that is, we need to get the result modulo p^a). We can precompute all p-free parts of the factorial and the maximum power of p that divides the factorial for all 0 <= n <= N in linear time using something like this:

   powers = [0] * (N + 1)
   p_free = [i for i in range(N + 1)]
   p_free[0] = 1
   for cur_p in powers of p <= N:
       i = cur_p
       while i < N:
           powers[i] += 1
           p_free[i] /= p
           i += cur_p
   

   Now the p-free part of the factorial is the product of p_free[i] for all i <= n and the power of p that divides n! is the prefix sum of the powers.

3. Now we can divide two factorials: the p-free part is coprime with p^a so it always has an inverse. The powers of p are just subtracted.

4. We're almost there. One more observation: we can precompute the inverses of p-free parts in linear time. Let's compute the inverse for the p-free part of N! using Euclid's algorithm. Now we can iterate over all i from N to 0. The inverse of the p-free part of i! is the inverse for i + 1 times p_free[i] (it's easy to prove it if we rewrite the inverse of the p-free part as a product using the fact that elements coprime with p^a form an abelian group under multiplication).

5. This algorithm runs in O(N * number_of_prime_factors + the time to solve the system using the Chinese remainder theorem + sqrt(MOD)) time per test case. Now it looks good enough.