提交时间:2024-02-27 15:59:38
运行 ID: 26937
#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; 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,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*qpow(j-k-1,K)%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*qpow(j-k+1,K)%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*qpow(j-k,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*qpow(j-k,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; }