自动搬运

查看原文

来自洛谷，原作者为

	Cx114514 不拿金鈎不改個簽

搬运于2025-08-24 23:07:47，当前版本为作者最后更新于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}$。

综上可得:

$g\left(k\right)=\begin{cases} \binom{m - cnt0 + cnt1 - 1}{cnt1 - 1}\times\binom{n - cnt1 + cnt0}{cnt0} & S_{k+1}=0 \\ \binom{n - cnt1 + cnt0 - 1}{cnt0 - 1}\times\binom{m - cnt0 + cnt1}{cnt1} & S_{k+1}=1 \end{cases}$

最终答案即为 $\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;
}