Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32612 | LYLAKIOIAKIOI | 【S】T2 | C++ | 运行出错 | 0 | 0 MS | 88 KB | 1683 | 2024-09-15 16:42:58 |
#include<bits/stdc++.h> #define rf(i,a,b) for(int i=(a);i<=(b);i++) #define rb(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; const int N=1e3+10,V=310; int mod=998244353; int n,v; int f[N][N][V];bool vis[N][N][V]; int fac[N*5],inv[N*5]; int invp[V*6][V*3]; int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*a*x%mod;b>>=1;a=1ll*a*a%mod; }return x; }int lim=4e3+10; int C(int up,int down){ return 1ll*fac[down]*inv[up]%mod*inv[down-up]%mod; }struct nd{ int id,sm,vl; }; int main(){ fac[0]=1;rf(i,1,lim) fac[i]=1ll*fac[i-1]*i%mod; inv[lim]=qp(fac[lim],mod-2);rb(i,lim-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod; rf(i,1,lim/3) invp[i][0]=1,invp[i][1]=1ll*inv[i]*fac[i-1]%mod; rf(j,2,lim/6) rf(i,1,lim/6) invp[i][j]=1ll*invp[i][j-1]*invp[i][1]%mod; cin>>v>>n; int ans=0; queue<nd> q;f[0][0][v]=fac[n]; q.push((nd){0,0,v}); while(!q.empty()){ nd p=q.front(); q.pop(); //cout<<p.id<<' '<<p.sm<<' '<<p.vl<<' '<<f[p.id][p.sm][p.vl]<<endl; if(p.sm>n) continue;//if(p.id*p.vl>n) continue; if(p.sm==n&&p.vl==0){ ans=(ans+1ll*f[p.id][p.sm][p.vl]*(p.id-1)%mod)%mod;continue; }if(p.vl==0) continue; rf(i,0,p.vl){ if(p.sm+i>n) continue; if(i*p.id+i>n) continue; f[p.id+1][p.sm+i][i]+=1ll*f[p.id][p.sm][p.vl]*C(i,p.vl)%mod*invp[p.id+1][i]%mod; f[p.id+1][p.sm+i][i]%=mod; //cout<<p.id+1<<' '<<p.sm+i<<' '<<i<<endl; if(!vis[p.id+1][p.sm+i][i]) vis[p.id+1][p.sm+i][i]=1,q.push((nd){p.id+1,p.sm+i,i}); } }cout<<ans%mod; return 0; }