Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
26938 | LYLAKIOI | 【BJ】T3 | C++ | 通过 | 100 | 127 MS | 3848 KB | 2019 | 2024-02-27 16:01:52 |
#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 x1 x114514 #define y1 y114514 #define p_b push_back #define m_p make_pair #define uint unsigned int using namespace std; typedef long long ll; const int maxn=2e5+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,m,K,pw[305]; ll dp1[2][305][305],dp2[2][305][305]; 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; } void slv(){ n=read(),m=read(),K=read(); if(n>m){ printf("0\n");return; }dp1[0][0][0]=0,dp2[0][0][0]=1; up(i,1,n)pw[i]=qpow(i,K); up(i,0,m-1){ int op=(i&1); up(j,0,n)up(k,0,j)dp2[!op][j][k]=0,dp1[!op][j][k]=0; up(j,0,n)up(k,0,j){ if(!dp2[op][j][k])continue; if(k+1<=j){ (dp2[!op][j][k+1]+=dp2[op][j][k])%=mod; (dp1[!op][j][k+1]+=dp1[op][j][k]+dp2[op][j][k]*1ll*pw[j-k-1]%mod)%=mod; } if(j+1<=n){ (dp2[!op][j+1][k]+=dp2[op][j][k])%=mod; (dp1[!op][j+1][k]+=dp1[op][j][k]+dp2[op][j][k]*1ll*pw[j-k+1]%mod)%=mod; } if(j+1<=n&&k+1<=n){ (dp2[!op][j+1][k+1]+=dp2[op][j][k])%=mod; (dp1[!op][j+1][k+1]+=dp1[op][j][k]+dp2[op][j][k]*1ll*pw[j-k]%mod)%=mod; } (dp2[!op][j][k]+=dp2[op][j][k])%=mod; (dp1[!op][j][k]+=dp1[op][j][k]+dp2[op][j][k]*1ll*pw[j-k]%mod)%=mod; } }printf("%d\n",dp1[m&1][n][n]); }int main(){ // freopen("segment.in","r",stdin); // freopen("segment.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }