algorithm - 使用恰好 k 个翻转操作生成的长度为 n 的不同二进制序列的数量

Question

考虑一个二进制序列 b 长度电话 .最初，所有位都设置为 0。我们定义了一个带 2 个参数的翻转操作，翻转(左，右) ，使得:

L 和 R 之间索引的所有位都被“翻转”，这意味着值为 1 的位变为值为 0 的位，反之亦然。更准确地说，对于 [L,R] 范围内的所有 i:b[i] = !b[i]。

指定范围之外的位没有任何 react 。

您需要确定可以使用 获得的可能不同序列的数量。正好 K 翻转运算以任意给定数字为模，我们称之为 MOD .
更具体地说，每个测试在第一行包含一个数字 电话 ，要给出的查询数量。然后有 T 个查询，每个查询的形式为 电话 , K , MOD 与上面的意思。

1 ≤ N，K ≤ 300 000

≤ 250

2 ≤ MOD ≤ 1 000 000 007

测试中所有 N-s 的总和 ≤ 600 000

时间限制:2 秒

内存限制:65536 KB

示例:
输入:
1
2 1 1000
输出:
3
说明:
有一个查询。初始序列为 00。我们可以进行以下操作:
翻转(1,1)⇒ 10
翻转(2,2)⇒ 01
翻转(1,2)⇒ 11
因此，恰好使用 1 次翻转可以生成 3 个可能的序列。

我所做的一些快速观察，虽然我不确定它们是否完全正确:
如果 K 足够大，也就是说如果我们有足够多的翻转可供我们使用，我们应该能够获得 2n 个序列。
如果 K=1，那么我们要寻找的结果是 N(N+1)/2。它也是 C(n,1)+C(n,2)，其中 C 是二项式系数。
目前正在尝试使用蛮力方法，看看我是否能发现某种规则。我认为这是一些二项式系数的总和，但我不确定。
我还遇到过这个问题的一个更简单的变体，其中翻转操作只翻转一个指定的位。在这种情况下，结果是
C(n,k)+C(n,k-2)+C(n,k-4)+...+C(n,(1 或 0))。当然，也有 k > n 的特殊情况，但差别不大。无论如何，很容易理解为什么会发生这种情况。我想这值得一提。

Answer 1

这里有一些想法:

我们可以假设没有翻转操作发生两次(否则，我们可以假设它没有发生)。它确实会影响操作的数量，但我稍后会谈到。

我们可以假设没有两个线段相交。确实，如果L1 < L2 < R1 < R2 ，我们可以做 (L1, L2 - 1)和 (R1 + 1, R2)翻转。一个段在另一个段内的情况类似处理。

我们也可以假设没有两个段相互接触。否则，我们可以将它们粘合在一起并减少操作次数。

这些观察结果给出了通过精确翻转 k 可以获得的不同序列数量的以下公式没有“冗余”翻转的段:C(n + 1, 2 * k)(我们选择段的 2 * k 端。它们总是不同的。左端是独占的)。

如果我们的表现不超过 K翻转，答案是 sum for k = 0...K of C(n + 1, 2 * k)

直觉上，似乎可以变换不超过K的序列。翻转为完全 K 的序列翻转(例如，我们可以将同一段再翻转两次并添加 2 个操作。我们也可以将包含两个以上元素的段拆分为两个段并添加一个操作)。

通过运行蛮力搜索(我知道这不是一个真正的证明，但结合上面提到的观察看起来是正确的)，如果 n 或 k 等于 1，则答案该总和减去 1，否则正好是总和。

即结果是 C(n + 1, 0) + C(n + 1, 2) + ... + C(n + 1, 2 * K) - d ，其中 d = 1如果 n = 1 or k = 1和 0除此以外。

这是我用来寻找运行蛮力搜索模式并验证公式对于小 n 是否正确的代码和 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)

这个解决方案比穷举搜索要好得多。例如，它可以运行在 O(N * K)如果我们使用帕斯卡三角形计算系数，则每个测试用例的时间。不幸的是，它不够快。我知道如何更有效地解决素数 MOD (使用卢卡斯定理)，但 O 在一般情况下没有解决方案。

乘模逆不能立即解决这个问题，因为 k!或 (n - k)!可能没有反模 MOD .

注意:我假设 C(n, m)为所有非负 n 定义和 m并且等于 0如果 n < m .

我想我知道如何为任意 MOD 解决它现在。

让我们分解 MOD成素因数 p1^a1 * p2^a2 * ... * pn^an .现在可以对每个素因数独立求解这个问题，并使用中国剩余定理组合结果。

让我们修复一个质数 p。让我们假设 p^a|MOD (也就是说，我们需要得到结果模 p^a )。我们可以预先计算所有 p -无部分阶乘和最大幂p将所有的阶乘除以 0 <= n <= N在线性时间内使用这样的东西:

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

现在p-free阶乘的一部分是 p_free[i] 的乘积所有 i <= n和 p 的除法幂 n!是 powers 的前缀和.

现在我们可以除以两个阶乘:p -free 部分与 p^a 互质所以它总是有一个逆。 p的权力只是减去。

我们快到了。另一个观察结果:我们可以预先计算 p 的倒数- 线性时间内的免费零件。让我们计算 N! 的无 p 部分的倒数使用欧几里得算法。现在我们可以遍历所有 i来自 N到 0。 p 的倒数i! 的免费部分是 i + 1 的逆次 p_free[i] (如果我们使用与 p^a 互质的元素在乘法下形成阿贝尔群这一事实，将无 p 部分的逆重写为乘积，则很容易证明这一点)。

该算法运行于 O(N * number_of_prime_factors + the time to solve the system using the Chinese remainder theorem + sqrt(MOD))每个测试用例的时间。现在看起来已经足够好了。