提交时间:2024-09-15 13:14:49
运行 ID: 32576
#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,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,jc[5005],jc_inv[5005],dp[2][305][1005][2],f[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; } int A(int n,int m){return jc[m]*1ll*jc_inv[m-n]%mod;} int C(int n,int m){return jc[m]*1ll*jc_inv[m-n]%mod*1ll*jc_inv[n]%mod;} void init(){ jc[0]=jc_inv[0]=1;up(i,1,5000)jc[i]=jc[i-1]*1ll*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); } void slv(){ n=read(),k=read();init(); up(i,0,n)dp[0][i][0][1]=C(i,n); int res=0; up(i,1,k){ int op=i&1; memset(dp[op],0,sizeof(dp[op])); up(j,0,n)up(w,0,min((i-1)*j,k)){ int s=(dp[!op][j][w][0]+dp[!op][j][w][1])%mod; if(!s)continue; //cout<<"? "<<j<<" "<<w<<"\n"; (dp[op][j][w][0]+=s)%=mod; up(o,1,min(n-j,(k-w)/i)){ (dp[op][j+o][w+i*o][1]+=s*1ll*A(o*i,k-w)%mod*1ll*f[i][o]%mod*1ll*C(o,n-j)%mod)%=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]); (res+=i*1ll*dp[op][n][k][1]%mod)%=mod; //printf("now %d\n",res); }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; }