记 \(f_{i,j}\) 表示前 \(i\) 个数分成 \(j\) 组的方案数。
首先你可以新增一个组，将当前这个数扔进去。那么 \(f_{i,j} \leftarrow f_{i-1,j-1}\)。
如果我们不新增一个组，那么我们可能的选择组别个数就是 \(j - \frac{i-1}{m}\) ，因为在此之前已经有 \(\frac{i-1}{m}\) 个与 \(i\) 模 \(m\) 同余的数被放进了某一个组。那么 \(f_{i,j} \leftarrow f_{i-1,j} \times (j - \frac{i-1}{m})\)。
直接做就好了，复杂度 \(\mathcal{O}(n^2)\)。
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define lowbit(x) x&-x
using namespace std;
const int N=5e3+10;
const int mod=998244353;
ll ans;
int n,m,T,f[N][N];
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
int main(){
n=read(),m=read();
f[0][0]=1;
for(register int i=1;i<=n;++i){
for(register int j=1;j<=i;++j){
f[i][j]=f[i-1][j-1];
f[i][j]=(f[i][j]+1ll*f[i-1][j]*(j-(i-1)/m)%mod)%mod;
}
}
for(register int i=1;i<=n;++i) printf("%d\n",f[n][i]);
return 0;
}