[ZJOI2019]麻将（DP+有限状态自动机）

首先只需要考虑每种牌出现的张数即可，然后判断一副牌是否能胡，可以DP一下，令f[i][j][k][0/1]表示到了第i位，用j次i-1,i,i+1和k次i,i+1,i+2，是否出现对子然后最大的面子数量，j,k∈[0,2]，转移也很容易。这样暴力枚举可以获得50pts的“好”成绩。

然后可以丢掉第一维，只考虑18个状态最大可能对子数，强制f值<=4，最大对子数<=7，发现状态不到5000种。

然后把所有状态预处理，丢掉重复的状态，把有用状态建在自动机上 $i$

$i$

#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
int n,tot,ans,c[5][5],fac[N],inv[N],has[N],f[2][N][405],ch[N][5];
struct node{
    int f[2][3][3],cnt;
    node(){memset(f,-1,sizeof f),f[0][0][0]=cnt=0;}
    bool operator<(const node&x)const
    {
        for(int i=0;i<2;i++)
        for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
        if(f[i][j][k]!=x.f[i][j][k])return f[i][j][k]<x.f[i][j][k];
        return cnt<x.cnt;
    }
}st[N];
void add(int&a,long long b){a=(a+b)%mod;}
map<node,int>S;
node trans(node u,int x)
{
    node ret;
    ret.cnt=min(u.cnt+(x>=2),7);
    for(int a=0;a<2;a++)
    for(int b=0;a+b<2;b++)
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    for(int k=0;k<3;k++)
    if(i+j+k+b*2<=x&&u.f[a][i][j]!=-1)
    ret.f[a+b][j][k]=max(ret.f[a+b][j][k],min(u.f[a][i][j]+i+(x-i-j-k-b*2)/3,4));
    return ret;
}
int dfs(node u)
{
    if(S.count(u))return S[u];
    if(u.cnt==7)return 0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(u.f[1][i][j]==4)return 0;
    st[++tot]=u,S[u]=tot;
    int pos=tot;
    for(int i=0;i<=4;i++)ch[pos][i]=dfs(trans(u,i));
    return pos;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x;i<=13;i++)scanf("%d%*d",&x),has[x]++;
    for(int i=0;i<=4;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    fac[0]=inv[0]=inv[1]=1;for(int i=2;i<=4*n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=4*n;i++)fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
    dfs(node());
    f[0][1][0]=1;
    for(int i=1;i<=n;i++)
    {
        memset(f[i&1],0,sizeof f[i&1]);
        for(int j=1;j<=tot;j++)
        for(int k=has[i];k<=4;k++)
        if(ch[j][k])
        for(int t=0;t<=(i-1)*4;t++)
        add(f[i&1][ch[j][k]][k+t],1ll*f[i-1&1][j][t]*c[4-has[i]][k-has[i]]);
    }
    for(int i=1,sum;i<=n*4-13;i++)
    {
        sum=0;
        for(int j=1;j<=tot;j++)add(sum,f[n&1][j][i+13]);
        add(ans,1ll*sum*fac[i]%mod*fac[4*n-13-i]);
    }
    ans=(1ll*ans*inv[4*n-13]+1)%mod;
    printf("%d",ans);
}

View Code