牛客网暑期ACM多校训练营（第六场） C

题意
你对n个集合进行n次操作，第i次操作都从第i个集合开始，每次操作可以向从i到n的集合中插入一个元素，元素范围为，n个集合为一个大集合，问你有多少个不同的大集合
思路
我们以n=4,m=4为例，先举一个4,4的两个集合


我们现在只看第n层，两个不同的集合的最后一层的元素都含有1,2,3，但是这两个集合是不同的两个集合，原因是数字出现的顺序会影响上一层的集合，所以最后一层元素的顺序是影响总的个数的，那么我们假设第n层由k个元素，方案数就是相当于从m个数中选k个数的排列数，即，选定好这k个数后，答案还不是，因为由于他可以插重复的元素，而重复的元素只与其他第一次出现有关，例如


这里是两个不同的集合，而不同的原因是来自于，2出现的位置，由于第一个元素是固定的如
1,1,1,2,1,2{1,2}，1,1,2,1,1,2{1,2}，第一个出现的数会把第二个出现的数的前面都填满，而第二个出现的数才对答案有贡献，所以就相当于在n-1个位置上填k-1个数即，那么答案就应该是，如何k从1枚举到min(n,m)，即

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
const long long mod=998244353;
const int N=1e6+5;
long long inv[N];
int main()
{
    inv[0]=inv[1]=1;
    for(int i=2; i<N; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        long long n,m;
        scanf("%lld%lld",&n,&m);
        long long ans=m%mod,sum=m%mod;
        long long m_=m%mod,n_=n%mod;
        for(int i=1; i<min(n,m); i++)
        {
            sum=sum*(m_-i)%mod*(n_-i)%mod*inv[i]%mod;
            ans=(ans+sum)%mod;
        }
        printf("Case #%d: %lld\n",cas++,(ans+mod)%mod);
    }
    return 0;
}