Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32592 | LYLAKIOI | 【S】T2 | C++ | 运行超时 | 65 | 1000 MS | 25580 KB | 2349 | 2024-09-15 14:48:07 |
#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair #define ppc __builtin_popcount using namespace std; typedef long long ll; const int maxn=1e6+10; const ll mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,k; ll jc[5005],jc_inv[5005],f[1005][1005],ret[1005]; int dp[2][305][1005]; ll A[1005][1005],C[1005][1005]; int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } ll gA(int n,int m){return jc[m]*jc_inv[m-n]%mod;} ll gC(int n,int m){return jc[m]*jc_inv[m-n]%mod*jc_inv[n]%mod;} void init(){ jc[0]=jc_inv[0]=1;up(i,1,5000)jc[i]=jc[i-1]*i%mod,jc_inv[i]=qpow(jc[i],mod-2); up(i,0,1000)up(j,0,1000)f[i][j]=qpow(jc_inv[i],j); up(i,0,1000)up(j,i,1000)A[i][j]=gA(i,j),C[i][j]=gC(i,j); } void slv(){ n=read(),k=read();init(); dp[0][0][0]=1; up(i,1,k){ int op=i&1; memset(dp[op],0,sizeof(dp[op])); up(j,0,n)up(w,((i^1)?j:0),min((i-1)*j,k)){ ll s=dp[!op][j][w]; //if(!s)continue; //cout<<"? "<<j<<" "<<w<<"\n"; int &qwq=dp[op][j][w]; qwq+=s; if(qwq>=mod)qwq-=mod; up(o,1,min(n-j,(k-w)/i)){ int M=(s*A[o*i][k-w]%mod)*(f[i][o]*C[o][n-j]%mod)%mod; int &qwq=dp[op][j+o][w+i*o]; //dp[op][j+o][w+i*o]+=M; //if(dp[op][j+o][w+i*o]>=mod)dp[op][j+o][w+i*o]-=mod; qwq+=M;if(qwq>=mod)qwq-=mod; } }//up(j,0,n)up(w,0,k)printf("dp[%d][%d][%d]=%d\n",i,j,w,dp[op][j][w][0]+dp[op][j][w][1]); up(o,0,n)(ret[i]+=dp[op][o][k])%=mod; //printf("now %d\n",res); }int res=0; up(i,1,k)(res+=(ret[i]-ret[i-1]+mod)%mod*1ll*i%mod)%=mod; cout<<res; }int main(){ //freopen("caged.in","r",stdin); //freopen("caged.out","w",stdout); slv(); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; fclose(stdin); fclose(stdout); return 0; }