[ABC217G] Groups 题解

link

\(dp\)。

设\(dp_{i,j}\)表示将 1 到 \(i\) 的人正好分成 \(j\) 组的方案数。

从两个方面考虑转移。

1.新加入的人新开了一个组

则\(dp_{i,j}=dp_{i-1,j-1}\)。

2.新加入的人加入了一个已有的组

则\(dp_{i,j}=dp_{i-1,j}\)。

但是有\(i\ mod\ m\)值相同的人不能再统一组这一限制。

所以要把不合法的情况减掉。

与\(i\ mod\ m\)值相同的一共有\(\frac{i-1}{m}\)个。

故\(dp_{i,j}=\frac{i-1}{m}dp_{i-1,j}\)。

综上,\(dp_{i,j}=dp_{i-1,j-1}+\frac{i-1}{m}dp_{i-1,j}\)。

时间复杂度：\(O(n^2)\)。

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e15
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=5005,M=1e3+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,dp[N][N];
//dp[i][j]:[1,i]刚好凑成j组的方案数. 
signed main(){n=read(),m=read();dp[0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=(dp[i-1][j-1]+(j-(i-1)/m)*dp[i-1][j])%mod;for(int i=1;i<=n;i++) printf("%lld\n",dp[n][i]);return 0;
}