P1641 [SCOI2010] 生成字符串
Tag：组合数学、卡特兰数、反射容斥
题目描述
\(\text{lxhgww}\) 最近接到了一个生成字符串的任务，任务需要他把 \(n\) 个 \(1\) 和 \(m\) 个 \(0\) 组成字符串， 但是任务还要求在组成的字符串中，在任意的前 \(k\ (0 \le k \le n+m)\) 个字符中，\(1\) 的 个数不能少于 \(0\) 的个数。现在 \(\text{lxhgww}\) 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
答案对 \(20100403\) 取模。
数据说明：
- \(1\leq m\leq n\leq 10^6\)
分析
首先看到这个题，如果学过卡特兰数的一定可以发现这题和卡特兰数高度相似， 只不过在卡特兰数中，两种元素的数量是相同的，而这个题中元素数量分别是 \(n\) 和 \(m\)。
我们尝试用卡特兰数的证明方式去解决这个题， 我们从头开始试图构造这个字符串，并且将其放到坐标轴上理解，假设我们从原点 \((0,0)\) 开始， 我们把有一个 \(1\)，看成从当前位置向右移动一步，有一个 \(0\) 看成向上移动一步， 那么显然，在 \(1\) 和 \(0\) 的数量固定的情况下，无论如何都会走到 \((n,m)\) 这个点。
那么从 \((0,0)\) 只能向右或者向上移动， 最后走到 \((n,m)\) 这个点的方案数量为 \(\displaystyle {{n+m} \choose {n}} = {{n+m} \choose {m}}\)， 这是算法竞赛中经典组合意义，从 \(n+m\) 步中钦定 \(n\) 步的方向或钦定 \(m\) 步的方向。
而对于题目中的约束，对于任意一个前缀的位置，\(1\) 的数量都不能少于 \(0\) 的数量， 也就是说对于 \(y = x\) 这条直线，我们构造的路径可以踏上 \(y = x\)，但是不能越过 \(y = x\)， 如上图所示，这是一条合法的路径该有的样子。
如果你熟悉卡特兰数，你应该知道接下来我们要做什么， 既然我们之前计算的走到 \((n,m)\) 这个点的路径数量， 其中肯定有若干条违背了“不能越过 \(y = x\) 直线”这个限制。 那么我们用总方案数，减去跨过了 \(y = x\) 这条直线的方案数就得到了答案， 接下来的问题是如何对于“越过了 \(y = x\) 的路径”进行计数。
如果你熟悉卡特兰数的推导，那么接下来的思路就很显然了。 如果一个路径越过了 \(y = x\) 这条直线，那么必定和直线 \(y = x + 1\) 有交点。
我们将这个非法的路径和直线 \(y = x + 1\) 的第一个交点命名为 \(T\)， 之后我们将交点 \(T\) 之后的路径对着直线 \(y = x + 1\) 进行对称翻转。
于是我们发现，原来一条到 \((n,m)\) 的路径被映射成了一条到 \((m-1,n+1)\) 的路径， 而且每一条不合法的路径都一定和 \(y = x + 1\) 存在一个交点， 也就是说每一条不合法的路径都可以被唯一映射成一条从原点，向右向上走，最后走到 \((m-1,n+1)\) 的路径。
如何计算点关于直线对称之后的位置
设直线为 \(ax + by + c = 0\)，点 \((x_0,y_0)\) 关于该直线对称的点为 \((x^{\prime},y^{\prime})\)。 之后我们记 \(\displaystyle d = \frac{ax_0 + by_0 + c}{a^2 + b^2}\)， 那么就有 \(x^{\prime} = x_0 - 2ad, \ y^{\prime} = y_0 - 2bd\)。
这个做法是把点先沿着直线的法向量投影到直线上，再翻过去。
于是我们知道了总方案数为 \(\displaystyle {n+m \choose m}\)， 不合法的方案数经过映射之后也可以进行计算 \(\displaystyle {n+m \choose m - 1}\)， 最后的答案就是 \(\displaystyle {n+m \choose m} - {n+m \choose m - 1}\)。
直接使用组合数计算即可。
代码实现
#define int long long
const int MOD = 20100403;
const int N = 2e6 + 5;
int fastPow(int a,int n) {
int ans = 1; a %= MOD;
while (n) {
if (n & 1) ans = (ans * a) % MOD;
a = (a * a) % MOD;
n >>= 1;
}
return ans;
}
void MissMissingYou() {
vector<int> fac(N + 1, 1), inv(N + 1, 1);
for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
inv[N] = fastPow(fac[N], MOD - 2);
for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
auto C = [&](int n, int k) -> int {
if (k < 0 || k > n) return 0;
return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
};
int n, m;
cin >> n >> m;
cout << (C(n + m, m) - C(n + m, m - 1) + MOD) % MOD << endl;
}
日志
本页面创建于 2025/9/10 17:55