思路：$f_{i,j}$ 代表前 $i$ 个数，当前结尾有连续 $j$ 个互不相同的数的所有数组的成本总和。转移从 $f_{i,j}\to f_{i+1,j+1}$ 和特殊的从 $f_{i,k}\to f_{i,1}$ 情况，第二种转移加上 $1$（因为成本加上了 $1$，同时有 $k$ 种数字，故乘以 $k$）

现在是 n^3 的，这样求助也比较清晰。但是感觉提前记录一下就能优化到 n^2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4010,mod=998244353;
int n,k;
ll f[N][N];
int main(){
    scanf("%d%d",&n,&k);
    f[1][1]=k;
    for(int i=1;i<n;i++){
    	for(int j=1;j<=min(i,k);j++){
    		if(j!=k)f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(k-j)%mod)%mod;
    		else f[i+1][1]=(f[i+1][1]+(f[i][j]+1)*k%mod)%mod;
			for(int c=1;c<=j;c++)
				f[i+1][c]=(f[i+1][c]+f[i][j])%mod;
    	}
    }
    ll ans=0;
    for(int i=1;i<=k;i++) ans=(ans+f[n][i])%mod;
    printf("%lld",ans);
    return 0;
}

没看出来有什么问题，qwq，题解写的好复杂，看不懂