The 2021 CCPC Weihai Onsite - M. 810975 题解
title: The 2021 CCPC Weihai Onsite - M. 810975 题解
date: 2021-11-25 19:04:21
tags: [inclusion-exclusion, combinatorics, math, FFT, team training]
mathjax: true
题意
Zayin进行了 \(n\) 场比赛, 获胜 \(m\) 局，其中最长连胜是 \(k\) ，问有多少种情况
思路
问题转化
考虑败场分割胜场（这是一个经典解法：隔板法），问题转化为
\[\sum _{i=1} ^{n-m+1} {x_i} = m \ (x_i \leq k) \]的非负整数解个数（整数拆分问题）。
\[\begin{aligned} G(x) &= \Bigg( \sum _{i=0} ^{k} x^i \Bigg) ^ {n-m+1} \\ &= (1+x+x^2+x^3+ \cdots +x^k) ^ {n-m+1} \\ &= \Bigg(\frac{1}{1-x} - \frac{x^{k+1}}{1-x} \Bigg) ^ {n-m+1} \end{aligned} \]TIP: 如果你打算跑NTT快速幂 / 生成函数展开，看到这里就结束了。
引理
\[\sum _{i=1} ^{p} {x_i} = m \]的非负整数解个数为
\[C(m+p-1,\ p-1) = C ^{p-1} _{m+p-1} \]引理证明
先考虑正整数解个数
考虑有 \(m\) 个球，分为 \(p\) 组，那么只需要这么考虑
O _ O _ O _ O _ O _ ....... _ O _ O // O 表示球, _ 表示空位
那么往空位塞入 \(p-1\) 个隔板即可，\(C(m-1,\ p-1)\)
再考虑非负整数解个数
令 \(y_i = x_i + 1\)
也就是考虑：先给每组球多塞一个球，作上述隔板法，就可以扩展到非负整数了
\[\begin{aligned} &\sum _{i=1} ^{p} x_i &= &\ \ m \\ &\sum _{i=1} ^{p} (x_i + 1) &= &\ \ m + p \\ &\sum _{i=1} ^{p} {y_i} &= &\ \ m + p \end{aligned} \]因为第三个式子正整数解个数即为 \(C(m+p-1,\ p-1)\)，也等于第一个式子的非负整数解个数
至此，我们得到了 \(n\) 场比赛，获胜 \(m\) 场的情况数
回到原问题
以和引理一样的思路，我们考虑某一场比赛 至少 赢了 \(k+1\) 次（因为组合的性质，我们不好解决恰好 \(k\) 次的问题），减去至少赢了 \(k\) 次就是答案了。
为了防止问题太过抽象，我们考虑 \(n=7,m=6,k=3,p=n-m+1=2\) 的情况，显然只有一种
首先，我们先抽一个 \(k\) 出来，算 \(\sum _{i=1} ^{p} {y_i} = y_1+y_2 = m - k = 3\) 情况数，然后 \(C(p,1)\) 塞给某1个 \(y_i\) ，即可保证得到的组合至少存在1个大于 \(k\) 的数。通过引理我们知道答案是 \(C(3+2-1, 2-1)\cdot C(2,1) = C(4,1) \cdot 2 = 8\)
同理，\(k+1\)也是这么算，得到答案 \(6\) ，但是 \(8 - 6 = 2 \not = 1\)
通过式子所代表的含义，我们列举出生成的 \(8\) 种 \(k\) 的组合和 \(6\) 种 \(k+1\) 的组合。（如果读者在这里没发现这里需要容斥，还请模拟一下8+6种情况，不会花太多时间）
发现不对，\(y_1 = y_2 = 3\) 被计入了 \(2\) 次。显然，这是因为+3计数重复。本质上，我们要求的是 y[1] >= 3 or y[2] >= 3 (记作 \(A\) ) ，但是我们这里算的是的是y[1] >= 3 + y[2] >= 3 (记作 \(B\) )，要想不重复，我们只能减去y[1] >= 3 and y[2] >= 3(记作 \(C\) )。即 \(A = B - C\)，同理，我们可以推广到 p > 2 的情况，即计算
\(i\) 表示枚举有 \(i\) 个元素 \(\geq k\)，左边那个组合数表示选 \(i\) 个数 \(+k\) ，右边那个组合数即为整数拆分非负整数解个数
\(k+1\) 同理。
最后
\[Answer = Ans|_k - Ans|_{k+1} \]小细节
具体看代码特判
代码
#include
using namespace std;
using i64 = long long;
const i64 MOD = 998244353;
const int N = 1e5 + 6;
i64 fac[N], inv[N], ifac[N];
void norm(i64 &x) {
while(x>=MOD) x -= MOD;
while(x<0) x += MOD;
}
i64 C(i64 n,i64 m) {
if(m<0 || n> n >> m >> k;
if(!(n>=m && m>=k)) {
cout << 0;
return 0;
}
if(k==0) {
if(m==0) cout << 1;
else cout << 0;
return 0;
}
vector a(m+2), b(m+2);
i64 w = m, f = n - m;
i64 ans = 0;
for(int i=1;i*k<=m;++i) {
// k
a[i] = C(f + 1, i) * C(m - i * k + f, f) % MOD;
// k + 1
b[i] = C(f + 1, i) * C(m - i * (k + 1) + f, f) % MOD;
ans += (i&1) ? (a[i] - b[i]) : (b[i] - a[i]);
norm(ans);
}
cout << ans;
return 0;
}