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

先从m个不同的颜色选k个然后排列即A(m,k),然后我们开始染色。
假如n为3，那么就是这个样子 _A1_A2_A3,然后把我们选的k种颜色(k<=n)***去然后把每种插入的颜色右边颜色都加上那种颜色。
第一个位置必须有一个颜色，这样才能保证A1不空。因为选颜色时已经排列过了，所以颜色序列也确定了。
那么剩下n-1个空，k-1种颜色就是C(n-1,k-1)。
那么答案就是singma(k(1->min(n,m))) A(m,k)C(n-1,k-1).

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int mod = 998244353;
const int maxn = 1000005;
ll inv[maxn+10];
int main()
{
    inv[1]=inv[0]=1;
    for(int i=2;i<maxn;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    int t;cin>>t;
    for(int ca=1;ca<=t;ca++)
    {
        ll n,m;cin>>n>>m;
        ll ans=0;
        ll sum=1;
        for(ll i=1;i<=min(m,n);i++)
        {
            sum=1ll*sum*((m-i+1)%mod)%mod;
            if(i>1)
            {
                sum=((1ll*sum*((n-i+1)%mod))%mod)*(inv[i-1])%mod;
            }
            ans=(ans+sum)%mod;
        }
        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}