题目描述：
你有n个不重复的集合，你每一次都要取一个大小为[1,m]的数，并把这些数放入第i到n个集合中。问你最多的可行的方案数。
题目分析：
这个题目我们可以转化为染色问题。考虑枚举最后有 k 种颜⾊，那么有种方案进行枚举。由于每种操作对⼀个后缀有影响，区分⽅案只要考虑第⼀个被影响的位置即可。 n 个位置放 k 种球，每个位置可以放多个，由隔板法⽅案数为
。而根据加法原理，最终的答案是1到min(n,m)中的类和
因此答案为：。之后就是喜闻乐见的推出公式求不出答案了。
我们队在做这个题的时候就犯了一个很低级的错误。我们误认为卢卡斯定理可以很高效的进行大组合数的运算，但是！！事实上卢卡斯定理在计算组合数的时间复杂度是O(log(模数))。而倘若模数相对比较大（如1e9+7）那么我们就需要用O(1e9+7)的时间预处理出逆元。而这显然在时间和空间上均是不支持的！！（注意：卢卡斯定理的运用条件一般在模数相对来说比较小如1e5的情况才最好使用，否则最好考虑其他方法求组合数）。
而这个题目显然是可以进行线性求解的！
我们将排列和组合均展开乘阶乘的形式，不难发现他们分别等于以及
。在更一般的，我们将这个分子化成
，
。可以发现，上述两个式子都是满足递推的关系的，因此我们直接用O(min(n,m))的时间求出答案.
代码：
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
typedef long long ll;
const int mod=998244353;
ll n,m;
ll inv[maxn];
void init(){
inv[1]=inv[0]=1;//线性求逆元
for(int i=2;i<=maxn;i++){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
}
int main()
{
int t;
scanf("%d",&t);
init();
int cnt=0;
while(t--){
scanf("%lld%lld",&n,&m);
ll a=m%mod,b=1;
ll res=0;
int len=min(n,m);
for(int i=1;i<=len;i++){
res=(res+a*b)%mod;
a=a*((m-i)%mod)%mod;
b=b*((n-i)%mod)%mod*inv[i]%mod;
}
printf("Case #%d: %lld
",++cnt,res);
}
return 0;
}