题面：
有 n 个人，要分成若干组，对于第 i 个人，它所在的组的人数不能超过 a i ，问分组的方案数模 998244353 的值。
组与组之间是不可区分的，每组的人也是无序的，但人与人之间是可以区分的。
数据范围
对于 10% 的数据，n ≤ 10。
对于 30% 的数据，n ≤ 50。
对于 50% 的数据，n ≤ 300。
对于 100% 的数据，n ≤ 2000,a i ≤ n。
显然我一开始是不会的，但经过wty大佬的耐心讲解还是明白了这个神奇的dp。
由于ai的限制使我们不能常规定义状态 f [ i ] [ j ] 为前 i 个人分成 j 组的方案数。
所以我们定义 f [ i ] [ j ] 为考虑租的大小为 [ i , n ] ，分完还剩 j 个人的方案数，我们从大到小枚举 i ，f [ 1 ] [ 0 ] 即为答案。
考虑转移，从 f [ i ] [ j ] 转移到 i - 1 ，设 c n t [ i ] 为 a 大小为i的个数，那么没分到组的就多了 c n t [ i - 1 ] 个人。那么对于这些人，我们枚举 k 代表选 k 个大小为 i - 1 的组，就相当于从 j + c n t [ i - 1 ] 中选取 k * ( i - 1 ) 个，并且将这 k * ( i - 1 ) 个人分成 k 组，预处理 g [ i ] [ j ] 为将 i 个人分成组 j 个的方案数。具体原理见注释。
代码：
#include<cstdio> #include<iostream> using namespace std; #define maxn 3000 #define mod 998244353 #define int long long int f[maxn][maxn],g[maxn][maxn],c[maxn][maxn],cnt[maxn]; int n; main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%lld",&n); for(int i=1; i<=n; i++) { int x; scanf("%lld",&x); cnt[x]++; } c[0][0]=1; for(int i=1; i<=n; i++) { c[i][0]=1; for(int j=0; j<=i; j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } //g[i][j]->把i个人分成每组j个人方案数 for(int j=1; j<=n; j++) { g[0][j]=1; for(int i=j; i<=n; i+=j) (g[i][j]=g[i-j][j]*c[i-1][j-1])%=mod; //为了避免重复，如（1,2）（3,4）和（3,4）（1,2）从g[i-j][j]转移过来时，对于剩下的大小为j的这一组，我们强制将最小的放到最前面，那么对于剩下的我们有i-1个，选取j-1个即可 //或者更简单的：g[i][j]=g[i-j][j]*c[i][j],用到g[i][j]的时候，除以 j!（就是不同块的排列数）->如（1,2）（3,4）和（3,4）（1,2），排除重复 } //f[i][j]代表分到大小为[i，n]的组，剩下j个人的方案数，所以f[1][0]为答案 f[n+1][0]=1; for(int i=n+1; i>1; i--) for(int j=0; j<=n; j++) for(int k=0; k*(i-1)<=j+cnt[i-1]; k++) (f[i-1][j+cnt[i-1]-k*(i-1)]+=f[i][j]%mod*c[j+cnt[i-1]][k*(i-1)]%mod*g[k*(i-1)][i-1]%mod)%=mod; printf("%lld\n",f[1][0]); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/11110623.html