HDOJ 7328 Snake —— 2023“钉耙编程”中国大学生算法设计超级联赛（5）（2023杭电多校第五场）

算法设计超级联赛（5）（2023杭电多校第五场）"/>

HDOJ 7328 Snake —— 2023“钉耙编程”中国大学生算法设计超级联赛（5）（2023杭电多校第五场）

题目链接

简要题意：题目相当于求 n n n个人排成 m m m个队伍，队伍内部有序，队伍之间无序，最长的长度不超过 k k k人的方案数。

题解：官方题解有多项式解法，作为多项式菜鸡，从来不写NTT的我写了一种广义容斥原理做法。

首先不难联想到小球入盒模型

n n n个相同的球放入 m m m个不同的盒子，每个盒子至少一个球的方案数，相当于在 n − 1 n-1 n−1个空位中插入 m − 1 m-1 m−1个隔板，有 C n − 1 m − 1 C_{n-1}^{m-1} Cn−1m−1​种方案。

可以先排列，转化为小球入盒模型

1、 n n n个不同人排成一队，有 n ! n! n!种方案。接下来的步骤 n n n个人应该看作相同的。

2、 n n n个相同的人分成 m m m段，最长的一段不超过 k k k人的方案数。相当于 n n n个相同的球放入 m m m个不同的盒子，每个盒子不超过 k k k个球的方案数。

这是一个经典的小球入盒模型+广义容斥原理的应用。

根据广义容斥原理：

假如有 n n n个不同的性质：
P k = P_k= Pk​= 至少满足 k k k个性质的元素个数
Q k = Q_k= Qk​= 恰好满足 k k k个性质的元素个数
则 Q k = ∑ i = 0 n − k ( − 1 ) i C k + i k P k + i Q_k=\sum\limits_{i=0}^{n-k}(-1)^iC_{k+i}^kP_{k+i} Qk​=i=0∑n−k​(−1)iCk+ik​Pk+i​
特别地： Q 0 = P 0 − P 1 + P 2 − P 3 + . . . Q_0=P_0-P_1+P_2-P_3+... Q0​=P0​−P1​+P2​−P3​+...

设该小球入盒问题的方案有 m m m个性质，第 i i i个性质是：第 i i i个盒子有大于 k k k个球

我们要求的是所有盒子的球都不超过 k k k个的方案数，即 Q 0 Q_0 Q0​

P i = n P_i=n Pi​=n个相同的球放入 m m m个不同的盒子，至少有 i i i个盒子有超过 k k k个球的方案数

求 P i P_i Pi​方法如下：（为了方便，令 k ′ = k + 1 k'=k+1 k′=k+1）

2.1、选出 i i i个盒子，有 C m i C_m^i Cmi​种选法。先在这 i i i个盒子中放入 k ′ k' k′个球，它们最终必然 ≥ k ′ \geq k' ≥k′个球，而其他盒子随意安排，就达到了至少有 i i i个盒子大于 k ′ k' k′个球的目的。

2.2、剩下的 n − i k ′ n-ik' n−ik′个相同的球放入 m m m个不同的盒子，其中在上一步选中的 i i i个盒子至少放 0 0 0个，另外 m − i m-i m−i个盒子至少放一个，有 C n − i k ′ + i − 1 m − 1 C_{n-ik'+i-1}^{m-1} Cn−ik′+i−1m−1​种方案（等价于先凭空借来 i i i个球，求出每盒至少 1 1 1球的方案数，得出方案后在 i i i个选中的盒子中收回一球）

得出 P i = C m i C n − i k ′ + i − 1 m − 1 P_i=C_m^iC_{n-ik'+i-1}^{m-1} Pi​=Cmi​Cn−ik′+i−1m−1​

根据广义容斥原理， Q 0 = ∑ i = 0 m ( − 1 ) i P i Q_0=\sum\limits_{i=0}^m (-1)^iP_i Q0​=i=0∑m​(−1)iPi​，注意到 m − 1 > n − i k ′ + i − 1 m-1>n-ik'+i-1 m−1>n−ik′+i−1即 i k > n − m ik>n-m ik>n−m时 C n − i k ′ + i − 1 m − 1 C_{n-ik'+i-1}^{m-1} Cn−ik′+i−1m−1​无意义， P i = 0 P_i=0 Pi​=0

3、当前 m m m个盒子是不同的，而按照题意盒子是相同的，因此要除以 m ! m! m!。

综上， a n s = n ! m ! ∑ i = 0 min ⁡ ( ⌊ n − m k ⌋ , m ) ( − 1 ) i C m i C n − i ( k + 1 ) + i − 1 m − 1 ans=\frac{n!}{m!}\sum\limits_{i=0}^{\min (\lfloor \frac{n-m}{k}\rfloor,m)}(-1)^{i}C_m^iC_{n-i(k+1)+i-1}^{m-1} ans=m!n!​i=0∑min(⌊kn−m​⌋,m)​(−1)iCmi​Cn−i(k+1)+i−1m−1​，时间复杂度为 O ( n ) O(n) O(n)，如果 i i i的循环上限搞不清楚，可以在组合数的函数里进行特判（代码里注释掉的部分），加上特判后就不用考虑组合数无意义的情况。比赛的时候加上这些特判通常可以避免一些细节上的错误，但是训练时应养成考虑完整的好习惯，避免给自己制造隐蔽的错误。有时候样例部分通过，可以考虑加上特判试一下，如果加上后顺利通过样例，说明很可能算上了一些无意义的组合数。

P S 1 PS_1 PS1​：这题做法类似，有兴趣的可以做一下，同样可以广义容斥原理或者多项式快速幂：The 2021 CCPC Weihai Onsite Problem-M 810975

P S 2 PS_2 PS2​：小球入盒模型可以根据球是否相同、盒是否相同、是否允许有空盒分为 8 8 8种情况，可以了解一下，三种需要斯特林数的我还不会。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+5;
const int mod=998244353;
ll fac[N],ifac[N];
ll qpow(ll a,ll b){ll s=1;for(;b;b>>=1){if(b&1)s=s*a%mod;a=a*a%mod;}return s;
}
ll C(int n,int m){
//	if(n<0||m<0||m>n)return 0;return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int n,m,k;
void work(){cin>>n>>m>>k;ll ans=0;int lim=min((n-m)/k,m);for(int i=0,f=1;i<=lim;++i){ans+=f*C(m,i)*C(n-i*(k+1)+i-1,m-1);ans%=mod;f*=-1;}ans=ans*fac[n]%mod*ifac[m]%mod;ans=(ans%mod+mod)%mod;cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);fac[0]=ifac[0]=1;for(int i=1;i<N;++i)fac[i]=fac[i-1]*i%mod;ifac[N-1]=qpow(fac[N-1],mod-2);for(int i=N-2;i;--i)ifac[i]=(i+1)*ifac[i+1]%mod;int T=1;cin>>T;while(T--){work();}
}