题目链接
简要题意：题目相当于求
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+ikPk+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=CmiCn−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)iCmiCn−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();
}
}
