将每一个ai表示为$ai=ki\cdot m+ri$，即满足$m\sum ki+\sum ri=n$且$0<ri<m$
枚举$S=\sum ri$（S范围是$k\le S\le k(m-1)$且与n同余，只有k个值），之后相当于让$\sum ki=(n-S)/m$，根据插板法以$o(k)$（c的定义）计算
还要计算出$\sum ri=S$的方案数，设f(i)表示有i个j满足$m\le rj$，其余无限制的方案数，那么答案就是$\sum_{i=0}^{k}(-1)^k\cdot f(k)$
f(i)的计算很简单，先是从k个数中选取i个，即c(k,i)；再将不满足的rj都减去m-1，即有n个数的和为$S-(m-1)i$的方案数，也用插板法，但可以o(1)计算（预处理阶乘即逆元）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define ll long long 5 #define N 25000005 6 int m,k,ans,fac[N],inv[N]; 7 ll n; 8 int c1(ll n,int m){ 9 int ans=1; 10 for(int i=0;i<m;i++)ans=1LL*(n-i)%mod*ans%mod; 11 return 1LL*ans*inv[m]%mod; 12 } 13 int c2(int n,int m){ 14 if (n<m)return 0; 15 return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; 16 } 17 int f(int n){ 18 int p=-1,ans=0; 19 for(int i=0;i<=k;i++){ 20 p*=-1; 21 ans=(ans+1LL*p*c2(k,i)*c2(n-(m-1)*i-1,k-1)%mod+mod)%mod; 22 } 23 return ans; 24 } 25 int main(){ 26 scanf("%lld%d%d",&n,&m,&k); 27 fac[0]=inv[0]=inv[1]=1; 28 for(int i=1;i<=k*m;i++)fac[i]=1LL*fac[i-1]*i%mod; 29 for(int i=2;i<=k*m;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod; 30 for(int i=1;i<=k*m;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod; 31 for(int i=0;i<k;i++){ 32 int j=i*m+n%m; 33 if ((j<k)||(k*(m-1)<j))continue; 34 ans=(ans+1LL*c1((n-j)/m+k-1,k-1)*f(j))%mod; 35 } 36 printf("%d",ans); 37 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11573890.html
