题解：P11487 「Cfz Round 5」Gnirts 10

Cx114514 · 2024-12-30 13:03:42 · 题解

题目链接：「Cfz Round 5」Gnirts 10

一道组合数学题。

场上对着一个错的式子 Debug 了两个小时，这下消愁了。

设 f\left(T\right)=k 的 T 的个数为 g\left(k\right)。

考虑怎么求 g\left(k\right)。

首先，S 的前 k 个元素一定按照顺序固定不变。设其中 0 的个数为 cnt0，1 的个数为 cnt1。则问题可以看作把剩余的 \left(m-cnt0\right) 个 0 和 \left(n-cnt1\right) 个 1 插入到这 k 个元素组成的序列中。

接下来考虑怎么插使得 f\left(T\right) 不变。

若 S_{k+1}=0，则 0 不能放在这 k 个元素后面，否则该元素会和 S_{k+1} 形成新的公共部分。则 0 只能插在这 k 个 1 之前（在插入的位置匹配到的一定是 1，0 不会产生影响）。而 1 可以插在原本的每个 0 前面以及整个序列后面。

可以看作把相同的 \left(m-cnt0\right) 个小球放入不同的 cnt1 个盒子里，可以有空盒子的方案数，答案为 \binom{m - cnt0 + cnt1 - 1}{cnt1 - 1} 。同理，插入 1 的方案数为 \binom{n - cnt1 + cnt0}{cnt0}。总方案数即为 \binom{m - cnt0 + cnt1 - 1}{cnt1 - 1}\times\binom{n - cnt1 + cnt0}{cnt0}。

若 S_{k+1}=1，同理可得方案数为 \binom{n - cnt1 + cnt0 - 1}{cnt0 - 1}\times\binom{m - cnt0 + cnt1}{cnt1}。

综上可得:

最终答案即为 \sum\limits_{k=1}^{n+m}k\times g\left(k\right)。

预处理阶乘及其逆元，时间复杂度 O\left(n+m\right)。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 2933256077;

int n, m, len, ans, cnt0, cnt1, fac[6000005], inv[6000005], facinv[6000005];

char c[6000005];

int C(int x, int y)
{
    if (x == y) return 1;
    if (x < y) return 0;
    if (y < 0) return 0;
    return (fac[x] * facinv[x - y] % mod) * facinv[y] % mod;
}

signed main()
{
    fac[0] = 1;
    for (int i = 1; i <= 6000000; i++)
        fac[i] = (fac[i - 1] * i) % mod;
    inv[1] = 1;
    for (int i = 2; i <= 6000000; i++)
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    facinv[0] = 1;
    for (int i = 1; i <= 6000000; i++)
        facinv[i] = facinv[i - 1] * inv[i] % mod;
    cin >> n >> m;
    len = n + m;
    for (int i = 1; i <= len; i++)
        cin >> c[i];
    for (int i = 1; i <= len; i++)
    {
        if (c[i] == '0') cnt0++;
        else cnt1++;
        int cur;
        if (c[i + 1] == '0') cur = C(m - cnt0 + cnt1 - 1, cnt1 - 1) * C(n - cnt1 + cnt0, cnt0) % mod;
        else cur = C(n - cnt1 + cnt0 - 1, cnt0 - 1) * C(m - cnt0 + cnt1, cnt1) % mod;
        ans = (ans + i * cur) % mod;
    }
    cout << ans << endl;
    return 0;
}