题目概述

解题报告

考试的时候看到这种题只能想不到+打不出来……一道SB剪枝我没加然后就只有暴力分 $20$ 了……

一副牌怎么样能胡？1.选出一种牌当对子，剩下的牌求出最大的面子 $\ge 4$ 。2.七对子。

先不管七对子，求出最多的面子可以直接DP，只要再记录一维：$f_{0/1,i,j,k}$ 表示有无对子，第 $i-1$ 种牌开头的顺子有 $j$ 个，第 $i$ 种牌开头的顺子有 $k$ 个且其余牌全部作为刻子的最大面子数。

然后我们要做的是加牌使得这个DP最后停在某些胡的状态，很明显是个DP套DP。

开一个结构体PAI，其中记录了 $f_{0/1,j,k},DZ​$ 表示DP状态以及对子数，一旦 $f_{1,0,0}\ge4\lor DZ\ge7​$ 就能胡。定义 $Trans(f,x)​$ 表示在DP状态 $f​$ 后面加一种新的牌 $x​$ 张得到的状态，$max(f,g)​$ 表示 $f,g​$ 两个状态中取最优得出来的状态，那么在PAI后面加一种新的牌 $x​$ 张得到的就是：

$$ f_0=Trans(f'_0,x)\\ f_1=max(Trans(f'_1,x),[x\ge 2]Trans(f'_0,x-2))\\ DZ=DZ'+[x\ge 2] $$

由于只要 $f_{1,0,0}\ge 4\lor DZ\ge 7​$ 就合法，所以我们可以将 $f​$ 中所有值与 $4​$ 取 $min​$ ，$DZ​$ 与 $7​$ 取 $min​$ 。然后进行大力DFS，发现不同的状态只有 $m=3956​$ 个，同时预处理 $son_{s,k}​$ 表示在 $s​$ 这个PAI后面加 $k​$ 到达的PAI。

接下来就是外层DP，因为要求的是最早胡牌巡目数 $i$ ，这个比较难求，我们可以转化为求巡目数为 $i$ 仍然没有胡的概率 $p_i$ ，然后利用期望公式 $E(x)=\sum_{i=14}^{4n-13}(i-13)P(x=i)=\sum_{i=13}^{4n-14}P(x>i)=\sum_{i=13}^{4n-14}p_i$ （证明戳这里）就可以得到答案。

定义 $f_{i,j,s}$ 表示前 $i$ 种牌选了 $j$ 张，到达了 $s$ 这个PAI的方案数，每次只需要枚举 $i$ 这种牌选了 $k$ 张，然后从 $f_{i-1,j,s}$ 转移到 $f_{i,j+k,son_{s,k}}$（其中 $son_{s,k}$ 不能是胡的状态），系数为 ${j+k-sum_i\choose k-a_i}A_{4-a_i}^{k-a_i}$ ，其中 $a_i$ 表示 $i$ 这种牌刚开始摸到了几张，$sum_i$ 表示 $\sum_{j=1}^{i}a_j$ ，即从 $4-a_i$ 张牌中选出了 $k-a_i$ 张进行排列，然后插入到之前的 $j$ 张牌中，不过由于有 $sum_i$ 张牌默认在最前面所以不能插入。

最后 $p_i$ 就是 $\sum_{s=1}^{m}f_{n,i,s}\over A_{4n-13}^{i-13}$ 。

示例程序

#include<map>
#include<cstdio>
#include<algorithm>
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100,maxm=3956,MOD=998244353;

int n,a[maxn+5];
struct data{
    int f[3][3];inline data() {for (int i=0;i<3;i++) for (int j=0;j<3;j++) f[i][j]=-1;}
    inline bool operator < (const data &a) const{
        for (int i=0;i<3;i++)
            for (int j=0;j<3;j++)
                if (f[i][j]!=a.f[i][j]) return f[i][j]<a.f[i][j];
        return false;
    }
    inline data operator * (int x){
        static data c;c=data();
        for (int i=0;i<3;i++)
            for (int j=0,F;j<3;j++)
                if (~(F=f[i][j]))
                    for (int k=0;k<3&&i+j+k<=x;k++)
                        c.f[j][k]=max(c.f[j][k],F+i+(x-i-j-k)/3);
        for (int i=0;i<3;i++) for (int j=0;j<3;j++) c.f[i][j]=min(c.f[i][j],4);return c;
    }
    inline void Fix(data c){
        for (int i=0;i<3;i++)
            for (int j=0;j<3;j++)
                f[i][j]=max(f[i][j],c.f[i][j]);
    }
};
struct PAI{
    data f[2];int DZ;inline PAI() {f[0].f[0][0]=DZ=0;}
    inline bool operator < (const PAI &a) const {return mp(mp(f[0],f[1]),DZ)<mp(mp(a.f[0],a.f[1]),a.DZ);}
    inline PAI operator * (int x){
        static PAI c;c.f[0]=f[0]*x;c.f[1]=f[1]*x;c.DZ=DZ;
        if (x>=2) c.f[1].Fix(f[0]*(x-2)),c.DZ=min(DZ+1,7);return c;
    }
    inline bool HU() {return DZ>=7||f[1].f[0][0]>=4;}
};
int m,son[maxm+5][5];bool HU[maxm+5];map<PAI,int> S;
int C[(maxn<<2)+5][(maxn<<2)+5],fac[(maxn<<2)+5],f[2][(maxn<<2)+5][maxm+5],ans;

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
inline void Make(int n){
    for (int i=C[0][0]=1;i<=n;i++) for (int j=C[i][0]=1;j<=i;j++) C[i][j]=ADD(C[i-1][j],C[i-1][j-1]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i);
}
int Dfs(PAI x,int st=1){
    if (S.count(x)) return S[x];int ID=(S[x]=++m);HU[ID]=x.HU();
    for (int i=0;i<=4;i++) son[ID][i]=Dfs(x*i,st+1);return ID;
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);Dfs(PAI());for (int i=1,x,y;i<=13;i++) scanf("%d%d",&x,&y),a[x]++;
    Make(n<<2);f[0][0][1]=1;
    for (int i=1,c=1,sum=0;i<=n;i++,c^=1){
        for (int j=0;j<=(i<<2);j++) for (int k=1;k<=m;k++) f[c][j][k]=0;sum+=a[i];
        for (int j=0;j<=(i-1<<2);j++)
            for (int s=1,G;s<=m;s++)
                if (G=f[c^1][j][s])
                    for (int k=a[i];k<=4;k++){
                        if (HU[son[s][k]]) continue;int &F=f[c][j+k][son[s][k]];
                        F=ADD(F,MUL(MUL(G,C[j+k-sum][k-a[i]]),MUL(C[4-a[i]][k-a[i]],fac[k-a[i]])));
                    }
    }
    for (int i=13;i<(n<<2);i++){
        int sum=0;for (int s=1;s<=m;s++) sum=ADD(sum,f[n&1][i][s]);
        ans=ADD(ans,MUL(sum,Pow(MUL(C[(n<<2)-13][i-13],fac[i-13]),MOD-2)));
    }printf("%d\n",ans);return 0;
}