The 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 bits are set to 0. We define a flip operation with two arguments, flip (L, R) , so that:

• All bits with indices between L and R are “inverted”, which means a bit with a value of 1, becomes a bit with a value of 0 and vice versa. More precisely, for all I in the range [L, R]: b [i] =! B [i].
• Nothing happens with bits outside the specified range.

You will be asked to determine the number of possible different sequences that can be obtained using exactly K operations with a flip file using an arbitrary given number, let's call it MOD .
More specifically, each test contains the number T in the first line, the number of queries that must be given. Then there are T queries, each of which has the form N , K , MOD with a value above.

• 1 ≤ N, K ≤ 300,000
• T ≤ 250
• 2 ≤ MOD ≤ 1 000 000 007
• The sum of all Ns in the test is <600,000
• time limit: 2 seconds
• memory limit: 65536 kb

---

Example:
Entrance:
1
2 1 1000
Output:
3
Explanation:
There is one request. The initial sequence is 00. We can perform the following operations:
flip (1,1) ⇒ 10
flip (2.2) ⇒ 01
flip (1,2) ⇒ 11
Thus, there are 3 possible sequences that can be generated using exactly 1 flip.

---

Some quick observations I made, although I'm not sure that they are absolutely correct:
If K is large enough, that is, if we have a sufficiently large number of flips, we can get 2 ⁿ sequences.
If K = 1, then the result we are looking for is N (N + 1) / 2. It is also C (n, 1) + C (n, 2), where C is a binomial coefficient.
You are currently trying to use brute force to see if I can define a rule. I think this is the sum of some binomial coefficients, but I'm not sure.
I also came across a slightly simpler version of this problem when the flip operation only flips one specified bit. In this case, the result is C (n, k) + C (n, k-2) + C (n, k-4) + ... + C (n, (1 or 0)). Of course, there is a special case when k> n, but this is not a huge difference. Anyway, it's pretty easy to see why this is happening. I think it's worth noting.

Answer 1

Here are some ideas:

• We can assume that the coup operation is not performed twice (otherwise we can assume that this did not happen). This affects the number of operations, but I will talk about this later.

• We can assume that the two segments do not intersect. Indeed, if L1 < L2 < R1 < R2 , we can simply do (L1, L2 - 1) and (R1 + 1, R2) flips. The case when one segment inside another is handled similarly.

• We can also assume that neither of the two segments touches each other. Otherwise, we can glue them together and reduce the number of operations.

• These observations give the following formula for the number of different sequences that can be obtained by turning exactly k segments without “redundant” flips: C (n + 1, 2 * k) (choose 2 * k ends of the segments, they are always different. The left end is exclusive )

• If we had completed no more than k flips, the answer would have been
  sum for k = 0...K of C(n + 1, 2 * k)

• It seems intuitively that his ability to transform a sequence of at most k turns into a sequence of exactly k flips (for example, we can flip the same segment two more times and add 2 we can also split a segment of more than two elements into two segments and add one operation).

• Having launched the brute force search (I know that this is not real evidence, but it looks correct in combination with the observations mentioned above), that the answer to this sum is minus 1 if n or k is 1 and exactly 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 the code that I used to search for patterns that perform brute force searches, and to validate formulas 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 an exhaustive search. For example, it can work in O(N * K) time for each test case, if we calculate the coefficients using the Pascal triangle. Unfortunately, this is not fast enough. I know how to solve it more efficiently for a simple MOD (using the Lucas theorem), but O has no solution in the general case.

Multiplicative modular inversions cannot solve this problem immediately, since k! or (n - k)! may not have the opposite modulo MOD .

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

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

• Let factorize MOD by prime factors p1^a1 * p2^a2 * ... * pn^an . Now you can solve this problem for each simple factor independently and combine the result using the Chinese remainder theorem.

• Let a prime p be fixed. Suppose that p^a|MOD (i.e., we need to get the result modulo p^a ). We can pre-compromise all p infinite parts of the factorial and the maximum power p , which 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 part of the p-free factorial is the product of p_free[i] for all i <= n , and the power of p dividing n! , is the prefix sum of powers .

• Now we can separate two factorials: the free part of p is coprime with p^a , so it always has the opposite. The forces p simply subtracted.

• We are almost there. One more note: we can precompute inversions of p free parts in linear time. Let the inverse be calculated for the p-free part of n! using the Euclidean algorithm. Now we can iterate over all i from n to 0. Inverse to the p -infinite part of i! is the inverse of i + 1 times p_free[i] (this is easy to prove if we rewrite the inverse of the p-free part as a product using the fact that the elements coinciding with p^a form an Abelian group when multiplied).

• This algorithm works in O(N * number_of_prime_factors + the time to solve the system using the Chinese remainder theorem + sqrt(MOD)) time for the test case. Now he looks good enough.

Answer 2

You are already on a good path with binomial odds. There are several factors to consider:

Think of your number as a binary string of length n . Now we can create another array counting the number of times the bit will be flipped:

 [0, 1, 0, 0, 1] number [a, b, c, d, e] number of flips. 

But even the number of coups leads to the same result, as well as all the odd numbers of coups. Thus, basically the corresponding part of the distribution can be represented by% 2

The next logical question is how many different combinations of even and odd values ​​are available. We will take care of the order later, and now just assume that a sorting array is ordered for simplicity. We start with k as a singular flip in an array. Now we want to add a flip. Since the entire flipping array is used by% 2, we must remove two from the k value to achieve this and insert them into the array separately. For instance:.

 [5, 0, 0, 0] mod 2 [1, 0, 0, 0] [3, 1, 1, 0] [1, 1, 1, 0] [4, 1, 0, 0] [0, 1, 0, 0] 

As the last example shows (remember that we are working modulo 2 in the final result), moving a single 1 does not change the number of flips in the final result. Thus, we should always flip the even bits of a number in an inverted array. If k even, so will the number of flipped bits, and vice versa, regardless of what the value of n .

So now the question is, how many different ways to fill an array are available? For simplicity, we will start with mod 2 right away.
Obviously, we start with 1 inverted bit if k is odd, otherwise with 1. And we always add 2 inverted bits. We can continue this until we flip all bits of n (or at least as many as we can flip)

 v = (k % 2 == n % 2) ? n : n - 1 

or we cannot propagate k further along the array.

 v = k 

Combining this:

 noOfAvailableFlips: if k < n: return k else: return (k % 2 == n % 2) ? n : n - 1 

So far so good, there are always v / 2 flipping arrays (mod 2) that differ in the number of upside down bits. Now we move on to the next part, rearranging these arrays. This is just a simple permutation function (exact repetition permutation):

 flipArrayNo(flippedbits): return factorial(n) / (factorial(flippedbits) * factorial(n - flippedbits) 

Putting it all together:

 solutionsByFlipping(n, k): res = 0 for i in [k % 2, noOfAvailableFlips(), step=2]: res += flipArrayNo(i) return res 

It also shows that for sufficiently large numbers we cannot get 2 ^ n sequences for the simple reason that we cannot organize operations as we please. The number of flips that really affect the result will always be even or odd depending on k . There is no way around this. The best result might be a 2^(n-1) sequence.

Answer 3

For completeness, a dynamic program is needed here. It can easily deal with an arbitrary module, since it is based on sums, but, unfortunately, I did not find a way to speed it up outside of O(n * k) .

Let a[n][k] be the number of binary strings of length n with k non-adjacent blocks of adjacent 1 that end in 1 . Let b[n][k] be the number of binary strings of length n with k non-adjacent blocks of adjacent 1 that end with 0 .

Then:

 # we can append 1 to any arrangement of k non-adjacent blocks of contiguous 1 # that ends in 1, or to any arrangement of (k-1) non-adjacent blocks of contiguous # 1 that ends in 0: a[n][k] = a[n - 1][k] + b[n - 1][k - 1] # we can append 0 to any arrangement of k non-adjacent blocks of contiguous 1 # that ends in either 0 or 1: b[n][k] = b[n - 1][k] + a[n - 1][k] # complete answer would be sum (a[n][i] + b[n][i]) for i = 0 to k 

It is interesting whether the following observations can be useful: (1) a[n][k] and b[n][k] are equal to zero when n < 2*k - 1 and (2) on the flip side, for values ​​of k greater than than (n + 1) / 2 & rfloor; the general answer seems identical.

Python code (for simplicity, full matrices are defined, but, in my opinion, at least one line is required for the bottom-up method):

 a = [[0] * 11 for i in range(0,11)] b = [([1] + [0] * 10) for i in range(0,11)] def f(n,k): return fa(n,k) + fb(n,k) def fa(n,k): global a if a[n][k] or n == 0 or k == 0: return a[n][k] elif n == 2*k - 1: a[n][k] = 1 return 1 else: a[n][k] = fb(n-1,k-1) + fa(n-1,k) return a[n][k] def fb(n,k): global b if b[n][k] or n == 0 or n == 2*k - 1: return b[n][k] else: b[n][k] = fb(n-1,k) + fa(n-1,k) return b[n][k] def g(n,k): return sum([f(n,i) for i in range(0,k+1)]) # example print(g(10,10)) for i in range(0,11): print(a[i]) print() for i in range(0,11): print(b[i])