首先可以先写个程序看每个数,有啥规律
代码:
#include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int Mod = 998244353; const int N = 5010; ll a[N][N]; int main(){ int n; while(cin>>n){ memset(a,0,sizeof a); a[1][1]=1; for(int i=0;i<=n+1;i++) for(int j=i;j>0;j--) for(int k=i;k>0;k--) a[j][k] += (a[j-1][k]+a[j][k-1])%Mod; for(int i=1;i<=n+1;i++){ for(int j=1;j<=n+1;j++) cout<<"\t"<<a[i][j]; cout<<endl; } } return 0; }
结果
发现规律:
代码:
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int Mod = 998244353; const int N = 5010; ll c[N][N]; void initComb(){ for(int i=0;i<=N;i++) c[i][0] = 1; for(int i=1;i<N;i++) for(int j=1;j<N;j++) c[i][j] = (c[i-1][j]+c[i-1][j-1])%Mod; } void bug(int n){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++) cout<<"\t"<<c[i][j]; cout<<endl; } } int main(){ int t,n,x,y; initComb(); cin>>t; while(t--){ cin>>x>>y>>n; if(n<x || n-x<y) cout<<0<<endl; else cout<<c[n][x]%Mod*c[n-x][y]%Mod<<endl; } return 0; }