题意:对于两个长度为\(K\)的数列\(\{a\}\)和\(\{b\}\)，满足\(\sum_{i=1}^Ka_i=N,\sum_{i=1}^Kb_i=M\)
对于这两个数列，定义权值为\(P=\prod_{i=1}^K\max \{0,\min\{a_i,b_i\}\}\)
求所有可能的数列的权值之和,答案取模\(998244353\)
\(1\leq K\leq N,M\leq 10^6\)
设\(g(k,n,m)\)表示\(a\)的和为\(n\),\(b\)的和为\(m\),长度为\(k\)的总权值
定义其生成函数\(f(x,y,z)=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^\infty g(i,j,k)x^iy^jz^k\)
不难得到递推式\(f=1+\sum_{i=1}^\infty ixy^iz^if(\frac{1}{1-y}+\frac{1}{1-z}-1)\)
\[f=f(\frac{1}{1-y}+\frac{1}{1-z}-1)\frac{xyz}{(1-yz)^2}+1\\f=f*\frac{1-yz}{(1-y)(1-z)}\frac{xyz}{(1-yz)^2}+1\\f=f*\frac{xyz}{(1-y)(1-z)(1-yz)}+1\\]
这样就可以直接计算了：枚举\((yz)^i\)之后直接通过组合数计算即可
\(g(n,m,k)=\sum_{i=0}^{\min(n,m)-k}{n-i-1\choose k-1}{m-i-1\choose k-1}{i+k-1\choose k-1}\)
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())==‘-‘&&(vis=1);while(‘0‘>k||k>‘9‘);
while(‘0‘<=k&&k<=‘9‘)t=(t<<3)+(t<<1)+(k^‘0‘),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
# define mod 998244353
ll fac[1000005],inv[1000005];
void init(const int N=1000000){
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=N;++i)fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=N;++i)inv[i]=inv[i-1]*inv[i]%mod;
}ll C(int x,int y){return x<y||y<0?0:fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main(){fre("easy");
init();
for(int T=read;T--;){
int n=read,m=read,k=read;
if(n<k||m<k){puts("0");continue;}
ll ans=0;
for(int i=0;i<=min(n,m)-k;++i){
int y=n-i,z=m-i;
ans=(ans+C(y-1,k-1)*C(z-1,k-1)%mod*C(i+k-1,k-1))%mod;
}printf("%lld\n",ans);
}
return 0;
}
所以这道题真的是本场考试最easy的\(\Huge ??????\)