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

consider binary sequence b of length n. initially, bits set 0. define flip operation 2 arguments, flip(l,r), such that:

• all bits indices between l , r "flipped", meaning bit value 1 becomes bit value 0 , vice-versa. more exactly, in range [l,r]: b[i] = !b[i].
• nothing happens bits outside specified range.

you asked determine number of possible different sequences can obtained using exactly k flip operations modulo arbitrary given number, let's call mod.
more specifically, each test contains on first line number t, number of queries given. there t queries, each 1 being of form n, k, mod meaning above.

• 1 ≤ n, k ≤ 300 000
• t ≤ 250
• 2 ≤ mod ≤ 1 000 000 007
• sum of n-s in test ≤ 600 000
• time limit: 2 seconds
• memory limit: 65536 kbytes

---

example :
input :
1
2 1 1000
output :
3
explanation :
there single query. initial sequence 00. can following operations :
flip(1,1) ⇒ 10
flip(2,2) ⇒ 01
flip(1,2) ⇒ 11
there 3 possible sequences can generated using 1 flip.

---

some quick observations i've made, although i'm not sure totally correct :
if k big enough, if have big enough number of flips @ our disposal, should able obtain 2ⁿ sequences.
if k=1, result we're looking n(n+1)/2. it's c(n,1)+c(n,2), c binomial coefficient.
trying brute force approach see if can spot rule of kind. think sum of binomial coefficients, i'm not sure.
i've come across simpler variant of problem, flip operation flips single specified bit. in case, result c(n,k)+c(n,k-2)+c(n,k-4)+...+c(n,(1 or 0)). of course, there's special case k > n, it's not huge difference. anyway, it's pretty easy understand why happens.i guess it's worth noting.

here few ideas:

1. we may assume no flip operation occurs twice (otherwise, can assume did not happen). affect number of operations, i'll talk later.

2. we may assume no 2 segments intersect. indeed, if l1 < l2 < r1 < r2, can (l1, l2 - 1) , (r1 + 1, r2) flips instead. case when 1 segment inside other handled similarly.

3. we may assume no 2 segments touch each other. otherwise, can glue them , reduce number of operations.

4. these observations give following formula number of different sequences 1 can obtain flipping k segments without "redundant" flips: c(n + 1, 2 * k) (we choose 2 * k ends of segments. different. left end exclusive).

5. if had perform no more k flips, answer
   sum k = 0...k of c(n + 1, 2 * k)

6. intuitively, seems possible transform sequence of no more k flips sequence of k flips (for instance, can flip same segment 2 more times , add 2 operations. can split segment of more 2 elements 2 segments , add 1 operation).

7. by running brute force search (i know it's not real proof, looks correct combined observations mentioned above) answer sum minus 1 if n or k equal 1 , sum otherwise.

that is, result c(n + 1, 0) + c(n + 1, 2) + ... + c(n + 1, 2 * k) - d, d = 1 if n = 1 or k = 1 , 0 otherwise.

here code used patterns running brute force search , verify formula correct small n , k:

reachable = set() = set()   def other(c):     """     returns '1' if c == '0' , '0' otherwise     """     return '0' if c == '1' else '1'   def flipped(s, l, r):     """     flips [l, r] segment of string s , returns result     """     res = s[:l]     in range(l, r + 1):         res += other(s[i])      res += s[r + 1:]     return res   def go(xs, k):     """     exhaustive search. used speed search avoid checking     same string same number of remaining operations twice.     """      p = (xs, k)     if p in was:         return     was.add(p)     if k == 0:         reachable.add(xs)         return     l in range(len(xs)):         r in range(l, len(xs)):             go(flipped(xs, l, r), k - 1)   def calc_naive(n, k):     """     counts number of reachable sequences running exhaustive search     """     xs = '0' * n     global reachable     global     = 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 formula shown above compute answer     """     res = 0             in range(k + 1):         res += cnk(n + 1, 2 * i)     if k == 1 or n == 1:         res -= 1     return res   if __name__ == '__main__':     # checks formula gives right answer small values of n , k     n in range(1, 11):         k in range(1, 11):                assert calc_naive(n, k) == solve(n, k) 

this solution better exhaustive search. instance, can run in o(n * k) time per test case if compute coefficients using pascal's triangle. unfortunately, not fast enough. know how solve more efficiently prime mod (using lucas' theorem), o not have solution in general case.

multiplicative modular inverses can't solve problem k! or (n - k)! may not have inverse modulo mod.

note: assumed c(n, m) defined non-negative n , m , equal 0 if n < m.

i think know how solve arbitrary mod now.

1. let's factorize mod prime factors p1^a1 * p2^a2 * ... * pn^an. can solve problem each prime factor independently , combine result using chinese remainder theorem.

2. let's fix prime p. let's assume p^a|mod (that is, need result modulo p^a). can precompute p-free parts of factorial , maximum power of p divides factorial 0 <= n <= n in linear time using this:

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

   now p-free part of factorial product of p_free[i] i <= n , power of p divides n! prefix sum of powers.

3. now can divide 2 factorials: p-free part coprime p^a has inverse. powers of p subtracted.

4. we're there. 1 more observation: can precompute inverses of p-free parts in linear time. let's compute inverse p-free part of n! using euclid's algorithm. can iterate on i n 0. inverse of p-free part of i! inverse i + 1 times p_free[i] (it's easy prove if rewrite inverse of p-free part product using fact elements coprime p^a form abelian group under multiplication).

5. this algorithm runs in o(n * number_of_prime_factors + time solve system using chinese remainder theorem + sqrt(mod)) time per test case. looks enough.