「ZJOI2019」麻将

传送门

Solution 

Code 

#include<bits/stdc++.h>

using namespace std;

#define reg register

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<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

const int P=998244353,C[5][5]={{1},{1,1},{1,2,1},{1,3,3,1},{1,4,6,4,1}};

int Mul(int x,int y){return (1ll*x*y)%P;}

int Add(int x,int y){return (x+y)%P;}

int n,w[15],t[105];

void rw(int &x,int y){if(min(y,4)>x)x=y;}

struct State

{

    int f[18],cnt;

    State(){memset(f,-1,sizeof f);f[0]=cnt=0;}

    bool operator <(const State&o)const

    {

        if(cnt!=o.cnt) return (cnt<o.cnt);

        for(int i=0;i<18;++i)

            if(f[i]!=o.f[i]) return (f[i]<o.f[i]);

        return false;

    }

    bool HU(){return cnt>=7||f[9]>=4;}

    friend State Trans(State a,int b)

    {

        register int i,j,k;State c;c.cnt=a.cnt+(b>=2);

        for(i=0;i<3;++i)for(j=0;j<3;++j)for(k=0;k<3&&i+j+k<=b;++k)

        {

            if(~a.f[i*3+j]) rw(c.f[j*3+k],a.f[i*3+j]+i+(b-i-j-k)/3);

            if(~a.f[i*3+j+9])rw(c.f[9+j*3+k],a.f[9+i*3+j]+i+(b-i-j-k)/3);

            if(i+j+k+2<=b&&~a.f[i*3+j]) rw(c.f[9+j*3+k],a.f[i*3+j]+i);

        }

        return c;

    }

}st[2100];int tot;int tr[2100][5];

std::map<State,int> mp;

int dfs(State cur)

{

    if(cur.HU()) return 0;

    if(mp.find(cur)!=mp.end()) return mp[cur];

    st[mp[cur]=++tot]=cur;int now=tot;

    for(int i=0;i<=4;++i) tr[now][i]=dfs(Trans(cur,i));

    return now;

}

int f[2][2100][405],fac[450],inv[450],ans;

int main()

{

    dfs(State());

    register int sum,i,j,k,l;

    for(inv[0]=inv[1]=fac[0]=fac[1]=1,i=2;i<=420;++i)

        fac[i]=Mul(fac[i-1],i),inv[i]=Mul((P-P/i),inv[P%i]);

    for(i=2;i<=420;++i) inv[i]=Mul(inv[i],inv[i-1]);

    n=read();

    for(i=1;i<=13;++i) w[i]=read(),read(),++t[w[i]];

    f[0][1][0]=1;

    for(sum=0,i=1;i<=n;sum+=t[i],++i)

    {

        memset(f[i&1],0,sizeof f[i&1]);

        for(j=1;j<=tot;++j)for(k=sum;k<=(i-1)<<2;++k)if(f[(i&1)^1][j][k])for(l=t[i];l<=4;++l)if(tr[j][l])

        {

            int nxt=tr[j][l];

            f[i&1][nxt][k+l]=Add(f[i&1][nxt][k+l],

                Mul(f[(i&1)^1][j][k],Mul(C[4-t[i]][l-t[i]],Mul(inv[k-sum],fac[k+l-sum-t[i]]))));

        }

    }

    ans=0;

    for(i=0;i<=(n<<2);ans=Add(ans,Mul(l,fac[(n<<2)-i])),++i)

        for(l=0,j=1;j<=tot;l=Add(l,f[n&1][j][i]),++j);

    printf("%d\n",Mul(ans,inv[(n<<2)-13]));

    return 0;

}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！