格子

小 A 有 m 个格子从左到右排开,同时有 n 种球,编号 1⋯n ,每个格子可以(且必须)放一种球。

当 对于每一个格子 i, i 右边所有格子中球的编号都不小于 i 中球的编号 时,小 A 会认为这种放球方案是合理的。

请你求出有多少种会让小 A 认为合理的方案,方案数对 998244353998244353 取模。

输入格式

一行两个整数 n,m 。

输出格式

一行一个整数,表示答案对 998244353 取模后的结果。

数据范围

1≤n,m≤1e6 。

样例输入

3 2

样例输出

6

隔板法:

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
const int maxn=1e6+100;
const int mod=998244353;
typedef unsigned long long ull;
ull qpow(ull a,ull b){
    ull ans=1;
    while(b){
        if(b%2){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b/=2;
    }
    return ans%mod;
}
int main(){
    ull n,m;
    cin>>n>>m;
    ull t1=1;
    ull tt=m+n-1;
    for(ull i=1;i<=m;i++)
    {
        t1=(1ull*t1%mod*tt%mod)%mod;
        tt--;
    }
    ull t2=1;
    for(ull i=1;i<=m ;i++) t2=(1ull*t2%mod*i%mod)%mod;
    ull ans=(1ull*t1%mod*qpow(t2,mod-2)%mod)%mod;
    cout<<ans%mod<<endl; 
}

 

上一篇:11.20 考试总结


下一篇:校赛G题代码backup