分组游戏

#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;
}