一、题目
无聊的校长 ( t DDXYX) 在写一些数列，他想出来一个问题想难倒你。
对于两个长度为 (k) 的数列 ({a},{b})，满足 (sum_{i=1}^ka_i=n,sum_{i=1}^kb_i=m)
对于这两个数列定义权值 (P=prod_{i=1}^kmin(a_i,b_i))，求 (sum_{{a},{b}}P) 对 (998244353) 取模的结果。
(n,m,kleq 5cdot 10^5)
二、解法
校长的做法
校长觉得我做不出来这么难的题，所以就把他绝妙的做法告诉我了~
寻找答案的组合意义，我们可以新定义一个数组 (c) 满足 (0leq c_i<min(a_i,b_i))
现在变成了一个嵌套计数问题，也即对于所有的 (a,b) 序列求出对应 (c) 序列的个数，贡献法考虑每个 (c) 序列贡献给了多少 (a,b) 序列，我们枚举 (c) 序列的总和 (i)，(a,b) 序列看成在原有的 (c) 序列上增加
校长牛逼！
构造版生成函数
如果从生成函数的角度考虑就是那个 (min(a_i,b_i)) 比较鬼畜，写方案数的生成函数还是比较容易的：
现在我们要让 (x^ay^b) 前面的系数是 (min(a,b))，因为我们尽量要用基本的生成函数表示，所以我们把它拆分成 (x^0y^0cdot x^ay^b+x^1y^1cdot x^{a-1}y^{b-1}...+x^{min(a,b)-1}y^{min(a,b)-1}cdot x^1y^1)，那么我们乘一个 ((x^0y^0+x^1y^1...)) 上去即可：
那么我们枚举 (x^iy^i) 的 (i)，然后剩下所有的方案数都可以用隔板法计算，就得到和校长方法一样的柿子了。
三、总结
组合意义一定要流畅，一开始我想的是放球，有鸡巴的意义
快速计算生成函数可以考虑拆分成基本形式，这时候就有点算贡献的思想了。
#include <cstdio>
#include <iostream>
using namespace std;
const int MOD = 998244353;
const int N = 500005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,k,ans,fac[N],inv[N];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
if(n<m || m<0) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
void work()
{
n=read();m=read();k=read();
int lim=min(n,m)-k;ans=0;
for(int i=0;i<=lim;i++)
ans=(ans+C(n-i-1,k-1)*C(m-i-1,k-1)%MOD*C(i+k-1,k-1))%MOD;
printf("%lld
",ans);
}
signed main()
{
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
T=read();init(5e5);
while(T--) work();
}