思路
- 先特判的情况,此时答案为0
- 我们可以枚举的值(0可以忽略),并可知一共有n-1~1种情况
因为最大值和最小值已经定了,那么其他的数在这两个值之间就行了
我们可以枚举m,有多少种情况
打表+oeis 可得
当时,即枚举0个数,可得 推出
当时,即枚举1个数,可得 推出
当时,即枚举2个数,可得 推出
当时,即枚举3个数,可得 推出
很容易看出规律
所以最终答案为
- 如果T的话,预处理下逆元
代码
// Problem: 比武招亲(上) // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/B // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=500010; const int INF=0x3f3f3f3f; const int mod=998244353; const double eps=1e-6; const double PI=acos(-1.0); ll n,m,ans; ll inv[N]; ll C(ll n,ll m,ll p){ ll ans = 1; for(ll i=1;i<=m;i++){ ans = ans * (n-m+i) % p; ans = ans * inv[i] % p; //求i模p的逆元 } return ans; } ll res[N];//res[i]=C(i+m-2,m-2,mod) void solve(){ cin>>n>>m; if(m==1){ cout<<"0\n"; return; } inv[1]=1; for(int i=2;i<=5e5;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod; res[1]=C(1+m-2,m-2,mod); rep(i,1,n-1){ if(i>1) res[i]=res[i-1]*(i+m-2)%mod*inv[i]%mod; ans+=i*(n-i)%mod*res[i]%mod; ans%=mod; } cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }