C++14(g++5.4) 解法, 执行用时: 67ms, 内存消耗: 45656K, 提交时间: 2019-09-07 16:56:17

#include<bits/stdc++.h>
#define Mod 998244353
#define ll long long
#define M 2005
using namespace std;
int n,m,k,s[M][M],sum[M][M],dp[M][M],pr[M];
int main() {
    scanf("%d%d%d",&n,&m,&k);
    pr[0]=1;
    for(int i=1; i<=n; i++) {
        pr[i]=1ll*pr[i-1]*i%Mod;
        for(int j=1; j<=i; j++) {
            if(j==1||j==i)s[i][j]=1;
            else s[i][j]=(s[i-1][j-1]+1ll*s[i-1][j]*j%Mod)%Mod;
        }
    }
    for(int i=0; i<=m; i++)sum[1][i]=1;
    dp[1][0]=1;
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            dp[i][j]=(sum[i-1][j-1]-(j-k>0?sum[i-1][j-k-1]:0)%Mod+Mod)%Mod;
            sum[i][j]=(sum[i][j-1]+dp[i][j])%Mod;
        }
    }
    ll ans=0;
    for(int i=1; i<=n; i++)ans=(ans+1ll*sum[i][m]*s[n][i]%Mod*pr[i]%Mod)%Mod;
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 69ms, 内存消耗: 45660K, 提交时间: 2018-10-01 23:34:06

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a),i##_(b);i<=i##_;++i)
using namespace std;
const int N=2005,p=998244353;
int n,m,k,a[N][N],f[N][N],jc[N],s[N][N],ans;
int main(){
	cin>>n>>m>>k;a[0][0]=jc[0]=1;
	REP(i,1,n)jc[i]=1ll*jc[i-1]*i%p;
	REP(i,1,n)REP(j,1,i)a[i][j]=(a[i-1][j-1]+1ll*a[i-1][j]*j)%p;
	REP(i,0,m)s[1][i]=1;f[1][0]=1;
	REP(i,2,n)REP(j,1,m)
		f[i][j]=(f[i][j]+s[i-1][j-1]-(j-k>0?s[i-1][j-k-1]:0))%p,s[i][j]=(s[i][j-1]+f[i][j])%p;
	REP(i,1,n)ans=(ans+1ll*s[i][m]*a[n][i]%p*jc[i])%p;
	cout<<(ans+p)%p;
	return 0;
}