提高组模拟赛 40 A. 子序列 题解
t1 笑传之 crash crash 标
题意略
首先有一个性质
对于所有由 \(c\) 个 \(0\)，\(d\) 个 \(1\) 组成的任意串，他对答案的贡献是相等的。
我不会证，但是 gpt 真好用：
证明
🧮 证明思路
我们要证明，对于任意由 \(c\) 个 0、\(d\) 个 1 组成的串 \(T\)，其贡献相等。
设：
- \(S\) 含 \(a\) 个 0、\(b\) 个 1；
- \(T\) 含 \(c\) 个 0、\(d\) 个 1；
- \(X = a - c\)，\(Y = b - d\)。
🧩 第一步：唯一化匹配
定义 左起最早匹配（Leftmost Embedding）：
从左向右匹配 \(T\) 在 \(S\) 中的最早出现位置，使得每个字符都取最靠左的合法位置。
由贪心性质可知匹配唯一。
🪜 第二步：分割成 gaps
根据匹配位置将 \(S\) 划分为 \(m+1\) 个间隙（gap）：
\(\text{gap}_0,\text{gap}_1,\ldots,\text{gap}_m\)
- 前 \(m\) 个 gap 各自禁止出现其后继字符；
- 第 \(m\) 个 gap（末尾）不受限制。
🧠 第三步：化为组合分配问题
设有：
- \(X\) 个额外 0 要放入 $d$ 个“允许放 0 的 gap”；
- \(Y\) 个额外 1 要放入 $c$ 个“允许放 1 的 gap”；
- 最后一个 gap 可任意放 \(z\) 个 0、\(w\) 个 1)。
则方案数为：
\( F(a,b,c,d) = \sum_{z=0}^{X}\sum_{w=0}^{Y} \binom{X-z+d-1}{d-1}\binom{Y-w+c-1}{c-1}\binom{z+w}{z} \)
（边界情形如 \(c=0\) 或 \(d=0\) 需作特判。）
🎯 结论
整个计数仅依赖于 \(a,b,c,d\)，与 \(T\) 的具体排列无关。
因此所有由 \(c\) 个 0、\(d\) 个 1 组成的串对答案的贡献相等。
所以我们现在可以把问题转化为所有由 \(a\) 个 \(0\)，\(b\) 个 \(1\) 组成的任意串，其中有子序列为 \(000...0111..11\)（ \(c\) 个 \(0\)，\(d\) 个 \(1\)）的个数。
通过组合数求解，从枚举子序列最后一个 \(0\) 位置的角度出发，当该位置为 \(i\) 时，前面的方案数为 \(C_{i-1}^{c-1}\)，后面的方案数为 \(C_{a+b-i}^{b+c-i}\)。
最后乘一个 \(C_{c+d}^d\) 即可。
若通过阶乘预处理组合数，时间复杂度为 \(O(n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define eb emplace_back
ll rd(){ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}return f*x;}
void writ(ll x){if(x<0){x=-x;putchar('-');}if(x>9)writ(x/10);putchar(x%10+'0');}
void wr(ll x){writ(x);puts("");}
void wr_(ll x){writ(x);putchar(' ');}
const ll N = 5e3+5, M = 1e9+7, inf = 0x3f3f3f3f;ll a, b, c, d;
ll f[N][N];void solve() {a = rd(), b = rd(), c = rd(), d = rd();f[0][0] = 1;for(ll i = 1; i <= a+b; i++) {f[i][0] = 1;for(ll j = 1; j <= i; j++) {f[i][j] = (f[i-1][j-1]+f[i-1][j])%M;}}ll ans = 0;for(ll i = c; i <= b-d+c; i++) {ans = (ans+f[i-1][c-1]*f[a+b-i][b+c-i]%M)%M;}ans = ans*f[c+d][d]%M;wr(ans);
}signed main() {freopen("suq.in", "r", stdin);freopen("suq.out", "w", stdout);ll T = 1;while(T--) solve();return 0;
}