BZOJ 2963 마작 DFS+ 동적 기획

제목의 대의: 불완전한 마작을 정해서 그 중에서 14장을 만져내어 화패를 구할 확률을 구한다. 패형은 일반 패형/칠대자/국사를 포함한다.
이 바보 같은 문제를 나는 어제 점심부터 지금까지 썼다.
답은 점수 형식이다. 우리가 화패의 방안수와 총 방안수 C14n을 구하고 약분하면 비교적 좋은 것은 C14n≈4.25∗1018이다.
카드형과 세 종류로 나뉘기 때문에 일반적인 사고방식은 세 가지 카드형의 확률을 각각 계산한 다음에 합치는 것이다. 그러나 이렇게 하면 안 된다. 왜냐하면 일반적인 카드형과 칠대자는 교차하는 것이기 때문에 이배구라고 부른다.
한 잔의 입구: 1번 문 전역, 패형에 두 폭의 동색 동수의 순자가 존재하는데, 이를 한 잔의 입구라고 부른다. 예를 들면 1m 1m 2m 2m 3m 3m 5m 5m 7m 7m 7m 9m 패형 중 1m 1m 2m 2m 2m 3m 3m가 바로 한 잔의 입구이다.
2컵 입구: 3번 문 전역, 패형에 두 폭의 1컵 입구가 존재하는데 이를 2컵 입구라고 부른다. 예: 1m 1m 2m 2m 3m 3m 5m 6m 6m 7m 7m 9m 9m
만약 두 잔의 입에서 중첩되지 않았다면(즉, 어떤 카드가 네 장 존재하지 않았는데, 1m 1m 2m 2m 3m 3m 3m 4m 4m 5m 7m 7m 이런 형식이 존재하지 않았다면) 두 잔의 입은 일곱 쌍을 만족시키는 형식이자 일반 패형을 만족시키는 형식이므로 답에서 빼야 한다는 것을 쉽게 발견할 수 있다.
고답=국사무쌍+칠대자+일반패형-겹치지 않는 두 잔입
국사무쌍: DP7대자: DP2컵 입구: DP/폭탄, DP를 사용한다면 같은 브랜드의 다른 해석 방식에 주의해야 한다. 예를 들어 1m 1m 2m 2m 3m 3m 4m 4m 5m 6m 6m 7m 7m는 세 가지 해석 방식이 있지만 한 번만 통계되어야 한다.
그리고 이 빌어먹을 일반 패형이야..
소박한 DP:fi, j, k, cnt1, cnt2는 현재 i장의 카드가 j조의 체면을 이루고 있음을 나타낸다. k=0/1은 유/무 장패를 나타낸다. 이때 i장의 카드는 cnt1장이 일치하지 않고 i-3-1장의 카드는 cnt2장이 일치하지 않는 방안 수가 남았다.
그러나 이렇게 DP가 나온 결과는 전혀 옳지 않다. 같은 패형에 다른 해석 방식이 있을 수 있기 때문이다. 3m 3m 3m 3m 4m 4m 4m 4m 4m 5m 5m 6m 6m 8m 8m 8m(3m 3m 3m)(4m 4m 4m 4m)(5m 5m 5m 5m)(8m 8m 8m 8m 8m)(6m 6m) 또는 (3m 4m 5m 5m)(4m 5m 6m)(4m 5m 6m)(4m 5m 6m)(4m 6m 6m)(8m 8m 8m 8m)(3m 8m)(3m 8m 8m) 8m 8m 8m(3m 8m) 7형 7m의 복잡한 해석 방법이 없기 때문이다. 일반패형
그리고 제가 검색을 해 봤는데 검색의 장점은 바로 해시가 무게를 판정할 수 있다는 것입니다. 이 문제를 잘 회피할 수 있습니다. 그리고 만약에 겉치레와 카드만 검색하면 검색량이 많지 않을 것입니다. 그리고 제가 측정해 봤는데 일반적인 카드형의 카드 수량은 1000W 정도입니다. 게다가 검색과 해시표의 덩어리 상수, MLE+TLE는 죽을 때까지 극한 데이터 그룹 4s로 난자를 가지고 놀았습니다.
그리고 meet-in-the-meedle을 생각해 보니 다양한 해석 방식의 문제를 피할 수 있는 좋은 방법이 없다는 것을 알게 되었다
DP 시간의 복잡도는 우수하지만 BUG가 있습니다.검색은 이 BUG를 피할 수 있지만 T가 죽을 때까지 이 두 가지 알고리즘을 결합하는 것을 고려해 보자
우리는 연결된 패를 하나의 연결 블록이라고 부른다. 예를 들어 1m 1m 2m 2m 3m 3m 5m 6m 6m 7m 8m 8m 이 패는 {1m 1m 2m 3m 3m} {5m 5m 6m 7m 8m 8m} 두 개의 연결 블록으로 나눌 수 있다.
같은 패형의 서로 다른 해석 방식의 문제가 연결 블록 내부에서만 나타나는 것을 쉽게 발견할 수 있다. 그러면 우리는 연결 블록을 검색한 다음에DP로 연결 블록을 조합할 수 있다.
연결 블록의 길이가 최대 9인 것을 감안하면 검색량이 49=262144를 넘지 않을 것이다
그 다음에 연결 블록 중 한 장의 카드가 1,2,3,4번 나타날 수 있다. 우리는 4진수로 cnti, j,k,sta를 검색하면 길이가 k이고 상태가sta인 연결 블록을 나타낸다. 그 중에서 i조의 체면과 j조가 카드를 사용하는 방안을 포함한다. 그리고 cnti, j,k가 서브집합을 뛰고 변환하면gi, j,k,sta는 k장이 연속되고 상태가sta인 카드 중 하나를 k로 선택한다.i조 체면과 j조 카드의 연결 블록을 포함하는 방안수
그리고...그리고 그냥 DP하면 돼요.
시간의 복잡도는 매우 현학적이지만 매우 빨리 달린다--

/* - - 1m 2m 3m 4m 5m 6m 7m 8m 9m - 1s 2s 3s 4s 5s 6s 7s 8s 9s - 1p 2p 3p 4p 5p 6p 7p 8p 9p - 1c - 2c - 3c - 4c - 5c - 6c - 7c */


#include <map>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int cnt[50],used[50];
long long C[140][20];
map<string,int> pos;
long long g[5][2][10][1<<18];
bool flag[10][1<<18];

void DFS(int i,int j,int k,int max_val,int hash)
{
    int temp=((1<<2*max_val)-1)/3;
    if(max_val && !flag[max_val][hash-temp])
        flag[max_val][hash-temp]=true,g[j][k][max_val][hash-temp]++;
    if(i>9) return ;

    int l;

    //    
    if(used[i]) DFS(i+1,j,k,max_val,hash);

    //    
    if(i<=7)
        for(l=1;l<=4-used[i] && l<=4-j;l++)
        {
            used[i]+=l;used[i+1]+=l;used[i+2]+=l;
            DFS(i+1,j+l,k,i+2,hash+(l<<(i-1)*2)+(l<<(i)*2)+(l<<(i+1)*2));
            used[i]-=l;used[i+1]-=l;used[i+2]-=l;
        }

    //  +  
    if(!k)
    {
        if(used[i]<=4-2)
        {
            used[i]+=2;
            DFS(i+1,j,k+1,max(max_val,i),hash+(2<<(i-1)*2));
            used[i]-=2;
        }
        if(i<=7)
            for(l=1;l<=4-2-used[i] && l<=4-j;l++)
            {
                used[i]+=l+2;used[i+1]+=l;used[i+2]+=l;
                DFS(i+1,j+l,k+1,i+2,hash+(l+2<<(i-1)*2)+(l<<(i)*2)+(l<<(i+1)*2));
                used[i]-=l+2;used[i+1]-=l;used[i+2]-=l;
            }
    }

    //  +  
    if(j!=4)
    {
        if(used[i]<=4-3)
        {
            used[i]+=3;
            DFS(i+1,j+1,k,max(max_val,i),hash+(3<<(i-1)*2));
            used[i]-=3;
        }
        if(i<=7)
            for(l=1;l<=4-3-used[i] && l<=4-1-j;l++)
            {
                used[i]+=l+3;used[i+1]+=l;used[i+2]+=l;
                DFS(i+1,j+l+1,k,i+2,hash+(l+3<<(i-1)*2)+(l<<(i)*2)+(l<<(i+1)*2));
                used[i]-=l+3;used[i+1]-=l;used[i+2]-=l;
            }
    }
}

void Pretreatment()
{
    int i,j,k,l1,l2,l3;
    C[0][0]=1;
    for(i=1;i<=136;i++)
    {
        C[i][0]=1;
        for(j=1;j<=14;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    }

    pos["1m"]=3;
    pos["2m"]=4;
    pos["3m"]=5;
    pos["4m"]=6;
    pos["5m"]=7;
    pos["6m"]=8;
    pos["7m"]=9;
    pos["8m"]=10;
    pos["9m"]=11;

    pos["1s"]=13;
    pos["2s"]=14;
    pos["3s"]=15;
    pos["4s"]=16;
    pos["5s"]=17;
    pos["6s"]=18;
    pos["7s"]=19;
    pos["8s"]=20;
    pos["9s"]=21;

    pos["1p"]=23;
    pos["2p"]=24;
    pos["3p"]=25;
    pos["4p"]=26;
    pos["5p"]=27;
    pos["6p"]=28;
    pos["7p"]=29;
    pos["8p"]=30;
    pos["9p"]=31;

    pos["1c"]=33;
    pos["2c"]=35;
    pos["3c"]=37;
    pos["4c"]=39;
    pos["5c"]=41;
    pos["6c"]=43;
    pos["7c"]=45;

    DFS(1,0,0,0,0);

    for(i=0;i<=4;i++)
        for(j=0;j<=1;j++)
            for(k=1;k<=9&&k<=i*3+j;k++)
                for(l1=0;l1<k*2;l1+=2)
                    for(l2=(1<<k*2)-1;~l2;l2--)
                    {
                        int temp=(l2>>l1)&3;
                        for(l3=0;l3<temp;l3++)
                            g[i][j][k][l2]+=g[i][j][k][l2^(temp<<l1)^(l3<<l1)]*C[temp+1][l3+1];
                    }
}

long long Calculate1()//    
{
    static const char s[][10]={"","1m","9m","1s","9s","1p","9p","1c","2c","3c","4c","5c","6c","7c"};
    static long long f[14][2];//f[i][j]       i  ， /       
    int i;
    memset(f,0,sizeof f);f[0][0]=1;
    for(i=1;i<=13;i++)
    {
        f[i][0]=f[i-1][0]*C[cnt[pos[s[i]]]][1];
        f[i][1]=f[i-1][0]*C[cnt[pos[s[i]]]][2]+f[i-1][1]*C[cnt[pos[s[i]]]][1];
    }
    return f[13][1];
}

long long Calculate2()//   
{
    static long long f[46][8];//f[i][j]      i  ，   j     
    int i,j;
    memset(f,0,sizeof f);f[0][0]=1;
    for(i=1;i<=45;i++)
    {
        f[i][0]=f[i-1][0];
        for(j=1;j<=7;j++)
            f[i][j]=f[i-1][j]+f[i-1][j-1]*C[cnt[i]][2];
    }
    return f[45][7];
}

long long Calculate3()//    
{
    static long long f[46][5][2];
    //f[i][j][k]      i  ，   j   ， /       
    int i,j,k,l1,l2,l3;
    memset(f,0,sizeof f);f[0][0][0]=1;
    for(i=1;i<=45;i++)
        for(j=0;j<=4;j++)
            for(k=0;k<=1;k++)
            {
                f[i][j][k]=f[i-1][j][k];
                int temp=0;
                for(l1=1;l1<=9 && cnt[i-l1+1];l1++)
                {
                    temp^=cnt[i-l1+1]-1<<(l1-1)*2;
                    for(l2=0;l2<=j;l2++)
                        for(l3=0;l3<=k;l3++)
                            f[i][j][k]+=f[i-l1-1][l2][l3]*g[j-l2][k-l3][l1][temp];
                }
            }
    return f[45][4][1];
}

long long Calculate4()//       
{
    static long long f[46][3][2];
    //f[i][j][k]      i  ，   j    ， /       
    int i,j,k,l;
    memset(f,0,sizeof f);f[0][0][0]=1;
    for(i=1;i<=45;i++)
        for(j=0;j<=2;j++)
            for(k=0;k<=1;k++)
            {
                f[i][j][k]=f[i-1][j][k];
                long long temp=1;
                for(l=1;l<=7;l++)
                {
                    temp*=C[cnt[i-l+1]][2];
                    if(!temp) break;
                    switch(l)
                    {
                        case 1:if(k)f[i][j][k]+=f[i-l-1][j][k-1]*temp;break;
                        case 3:if(j)f[i][j][k]+=f[i-l-1][j-1][k]*temp;break;
                        case 4:if(j&&k)f[i][j][k]+=f[i-l-1][j-1][k-1]*temp;break;
                        case 6:if(j>=2)f[i][j][k]+=f[i-l-1][j-2][k]*temp;break;
                        case 7:if(j>=2&&k)f[i][j][k]+=f[i-l-1][j-2][k-1]*temp;break;
                    }
                }
            }
    return f[45][2][1];
}

int main()
{
    int T,n,i;
    char p[10];
    Pretreatment();

    for(cin>>T;T;T--)
    {
        memset(cnt,0,sizeof cnt);
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%s",p),cnt[pos[p]]++;
        long long a=Calculate1()+Calculate2()+Calculate3()-Calculate4();
        long long b=C[n][14];
        long long gcd=__gcd(a,b);
        a/=gcd;b/=gcd;
        printf("%lld/%lld
",a,b);
        //cout<<_<<endl;
    }

    return 0;
}