QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#664019#3686. 麻将ccccccyd100 ✓642ms6440kbC++144.7kb2024-10-21 18:58:022024-10-21 18:58:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-21 18:58:04]
  • 评测
  • 测评结果:100
  • 用时:642ms
  • 内存:6440kb
  • [2024-10-21 18:58:02]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define LL __int128
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(int i(r),i##end(l);i>=i##end;--i)
using namespace std;
const string mhj[50]={"","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"};
unordered_map<string,int> id; int n,c[50];

namespace s1{
    LL f[8];
    LL calc(){//7*2(互不相同!)
        memset(f,0,sizeof(f));
        f[0]=1;
        rep(i,1,34){
            int v=c[i]*(c[i]-1)/2;
            if(v==0) continue;
            //贡献2张牌 : c[i]*(c[i]-1)/2
            per(k,7,1) f[k]=(f[k]+f[k-1]*v);
        }
        return f[7];
    }
}
namespace s2{
    LL get(){
        LL res=1;
        rep(k,0,2) res*=c[1+k*9];//s0=1
        rep(k,0,2) res*=c[9+k*9];//s0=9
        rep(k,1,7) res*=c[27+k];//s1=c
        return res;
    }
    LL calc(){//枚举重复
        LL ans=0;
        rep(k,0,2) ans+=(c[1+k*9]--)*get(),c[1+k*9]++;//s0=1
        rep(k,0,2) ans+=(c[9+k*9]--)*get(),c[9+k*9]++;//s0=9
        rep(k,1,7) ans+=(c[27+k]--)*get(),c[27+k]++;//s1=c
        return ans/2;//每个会被算两遍
    }
}
namespace s3{
    int w[10],k; vector<int> d(10); __int128 f[2][5],dp[2][5];
    int C(int x,int y){
        int sm=1;
        rep(i,0,y-1) sm=sm*(x-i);
        rep(i,1,y) sm=sm/i;
        return sm;
    }
    map<vector<int>,bool> vis;
    void dfs(int f0,int cnt){
        if(vis[d]) return ; vis[d]=1;
        // printf("%d %d : ",f0,cnt);
        // rep(i,1,9) printf("%d ",d[i]); puts("");
        ll res=1;
        rep(i,1,9) res=res*C(w[i],d[i]);
        f[f0][cnt]+=res;
        if(cnt>=4) return ;
        //枚举T(3)
        rep(i,1,9) if(w[i]-d[i]>=3) d[i]+=3,dfs(f0,cnt+1),d[i]-=3;//K(3)
        if(k!=3) rep(i,1,7) if(w[i]-d[i]&&w[i+1]-d[i+1]&&w[i+2]-d[i+2]){//S(3)
            d[i]++,d[i+1]++,d[i+2]++;
            dfs(f0,cnt+1);
            d[i]--,d[i+1]--,d[i+2]--;
        }
    }
    LL calc(){
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(k=0;k<=3;k++){//s1!=c
            rep(i,1,9) w[i]=c[i+k*9];
            memset(f,0,sizeof(f)); vis.clear();

            //枚举 K(2)
            dfs(0,0);//不选
            rep(i,1,9) if(w[i]>=2) d[i]+=2,dfs(1,0),d[i]-=2;//选

            // cerr<<k<<'\n';
            // rep(i,0,1) rep(j,0,4) cerr<<i<<' '<<j<<' '<<(ll)f[i][j]<<'\n';
            per(I,1,0) per(J,4,0){
                rep(i,0,I) rep(j,0,J) if(i+j){
                    dp[I][J]+=dp[I-i][J-j]*f[i][j];
                }
            }
        }
        return dp[1][4];
    }
}
namespace s4{
    int coef(int i,int j,int k){
        if(mhj[i][1]==mhj[j][1]&&mhj[i][1]==mhj[k][1]&&j+3==i&&i+1==k) return 2;
        if(mhj[i][1]==mhj[j][1]&&mhj[i][1]==mhj[k][1]&&j+3==k&&k+3==i) return 2;
        if(mhj[i][1]==mhj[j][1]&&mhj[i][1]==mhj[k][1]&&i+1==j&&j+3==k) return 2;
        if(mhj[i][1]==mhj[j][1]&&(i==j+3||i==j-1)) return 3;
        if(mhj[i][1]==mhj[k][1]&&(i==k+3||i==k-1)) return 3;
        return 6;
    }
    LL calc(){//O(7*34^3)
        LL ans=0,res;
        rep(i,1,34){//K(2)
            for(int j=1;j<=25;j=j+(j%9==7?3:1)){//[j,j+2]<=27
                for(int k=j;k<=25;k=k+(k%9==7?3:1)){//[k,k+2]<=27
                    if((j<=i&&i<=j+2)||(k<=i&&i<=k+2)||(min(j+2,k+2)-max(j,k)+1>0)) continue;//7组之间不能有相同
                    res=c[i]*(c[i]-1)/2;
                    rep(x,j,j+2) res=res*c[x]*(c[x]-1)/2;
                    rep(x,k,k+2) res=res*c[x]*(c[x]-1)/2;
                    // if(res) cerr<<i<<' '<<j<<" "<<k<<"   "<<coef(i,j,k)<<'\n';
                    ans+=res*coef(i,j,k);
                }
            }
        }
        return ans/6;
    }
}

LL C(int x,int k){
    LL sm=1;
    rep(i,0,k-1) sm=sm*(x-i);//k次下降幂
    rep(i,1,k) sm=sm/i;//k的阶乘
    return sm;
}
void write(LL x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }
void print(LL a,LL b){
    LL t=gcd(a,b);
    a/=t,b/=t;
    write(a),putchar('/'),write(b),puts("");
}
void solve(){
    memset(c,0,sizeof(c));
    scanf("%d",&n);
    string t;
    rep(i,1,n) cin>>t,c[id[t]]++;
    // write(s1::calc()),puts("");
    // write(s2::calc()),puts("");
    // write(s3::calc()),puts("");
    // write(s4::calc()),puts("");
    print(s1::calc()+s2::calc()+s3::calc()-s4::calc(),C(n,14));
}
signed main(){
    // freopen("z.in","r",stdin);
    // freopen("z.out","w",stdout);
    rep(i,1,34) id[mhj[i]]=i;
    int T=1;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}//g++ -g C.cpp -o my -std=c++14 -Wall

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 2ms
memory: 3796kb

input:

10
20
4s 4p 3s 5s 1c 9p 2m 6s 2p 9m 8p 8m 7m 1p 6s 6m 5m 5p 4m 7p
17
1c 8m 3m 6s 1c 6c 6c 8m 3c 8p 7p 6c 4p 2m 5s 7p 7s
18
3p 6s 4s 3m 2p 7c 7p 7p 6s 2m 5c 8m 1p 2s 8s 3c 2c 4p
16
8p 2c 7m 4s 3p 7m 3s 3m 7s 2m 5c 4m 3c 5p 1m 1m
19
3c 6s 9m 7c 4c 8p 5s 3m 4c 1c 8m 1s 8p 4s 6s 8p 5s 3c 9m
18
2m 4m 7c ...

output:

1/38760
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
1/1

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 2ms
memory: 4008kb

input:

10
20
9m 3c 7c 5s 2p 9p 1s 9s 8p 6p 3s 6c 2p 1s 5p 2c 2m 2m 8p 9s
19
1p 6p 5s 6s 1c 2m 1p 8m 5s 4s 3c 2c 3p 3p 7c 7s 4c 6s 1m
22
7c 8m 5m 2m 7m 2p 5p 8m 1c 3s 6m 8p 5c 3p 5s 9s 7m 8s 9m 6s 4c 3p
25
3m 8m 9p 7p 4s 6p 4m 2p 2m 7m 2p 4c 6m 8s 7c 4s 7s 6s 4p 9m 7s 6p 5p 3p 5c
23
5m 7s 9m 8m 6c 5c 3p 7c ...

output:

0/1
0/1
0/1
1/44574
0/1
4/159885
0/1
0/1
0/1
0/1

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 2ms
memory: 3780kb

input:

10
23
7c 4c 7s 8p 3s 5c 1s 4m 4s 4s 5c 1p 7c 4p 8s 6p 7s 1p 1m 2m 6m 9p 2s
22
4c 7p 3m 6m 5m 3m 1m 5c 8m 9p 5c 1p 1p 5m 6s 3p 8m 7p 1c 2c 4p 5m
25
7s 2m 1m 3p 9s 5s 8p 4s 4s 4m 8s 2p 8m 5m 1c 1m 9p 2s 1s 1p 3m 2c 2c 4c 8s
20
9p 6c 1p 3c 6p 8p 3s 5m 4s 1c 1s 3s 4m 2m 2s 6p 8p 2c 4s 7p
22
5p 5s 4m 6m ...

output:

0/1
0/1
0/1
0/1
1/319770
0/1
0/1
0/1
0/1
0/1

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 2ms
memory: 4012kb

input:

10
19
6m 3c 8p 5s 1m 8m 7c 1m 3s 6p 1s 5c 9m 4p 7p 4p 2p 3c 6s
24
7s 6m 4m 8s 3s 1s 1s 2m 1m 5m 5p 6s 4c 5m 3m 7p 1c 4c 7s 4s 2m 8p 9p 5p
25
8m 1s 3c 4m 4m 6p 8p 2p 8p 9m 9p 3p 1p 9s 6s 4c 4p 5p 7m 7p 4p 7s 6c 2m 6p
25
6s 2p 3p 5m 4s 7m 9p 8s 4p 9m 7s 3c 1m 5p 2c 2s 8p 7p 3s 3m 2m 7p 4c 5m 4p
20
3c ...

output:

0/1
1/81719
3/742900
3/371450
0/1
0/1
0/1
0/1
0/1
0/1

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 198ms
memory: 6140kb

input:

10
109
5c 3p 4c 8s 3s 6s 7s 1s 3c 7p 4p 6s 3s 5s 1c 5s 7m 3c 6c 3m 9p 7c 9p 7c 3s 2c 4m 2s 1c 1m 6m 1m 2s 1s 1p 2p 7c 4s 3p 9m 2m 8p 5c 8p 1p 3p 5m 4m 6c 7s 3m 2p 4s 8p 6m 6p 6s 7p 9s 7m 6c 4s 4c 3c 4p 3c 8m 7p 8m 7s 3m 3s 2c 9m 8m 2c 3m 9p 6m 1s 8s 6s 7m 1m 6c 4p 5m 8m 2s 8s 2m 1p 7s 5p 5c 5p 2p 1p...

output:

438517325999/160330885263858960
5519303885/1767477707092944
315803459/210200461893180
1113059528533/404822104630406520
100726669633/44186942677323600
1800166337/584725152763800
247005179741/91748617512913200
40299842873/12428282928826440
118862116391/59458448728028700
2580573199/868119825121065

result:

ok 10 lines

Test #6:

score: 10
Accepted
time: 296ms
memory: 6232kb

input:

10
103
1c 3p 6m 1s 2m 7m 1c 9s 2s 3c 6p 7m 3c 9s 5p 1p 8p 1s 4c 8s 1m 1p 7s 6p 3c 2c 8m 3p 4s 3m 7p 6p 7p 1c 2s 8m 7s 7c 5p 1m 2p 6c 7m 5c 7p 4c 2s 6c 3m 3m 5s 9p 9s 1s 4p 7m 6s 3s 7s 9m 8p 4c 1m 8m 8s 8p 5s 6s 4p 3m 3s 7c 6c 8s 5c 2p 7c 4s 5m 4m 9p 7s 3p 4c 6c 5m 7p 9m 7c 8m 1s 2c 9s 5m 1p 5c 3s 6s...

output:

4357204237/2023866562784850
923931927481/347808183330273600
57714372151/17427686431277403
300638747/144154304891880
120055658171/38320539030548190
300343959787/118654754805463980
412046647693/189250121876392170
517695872597/137118194912492700
18873223157/5997113535284730
316898500244/83676706780057695

result:

ok 10 lines

Test #7:

score: 10
Accepted
time: 500ms
memory: 6376kb

input:

10
133
1s 1s 7p 4s 1p 9s 7m 3p 6s 8s 2s 9p 3s 7s 8s 2m 4p 6m 7c 9s 7m 1c 6p 5p 5m 5p 1c 3p 1m 3s 9s 5c 2m 5s 9s 4p 4m 6c 6s 3s 3m 5s 8s 6m 2c 6p 4p 5p 6c 8m 4c 4p 8p 7c 1s 9p 1p 2c 4c 9m 1m 5c 2m 7c 8p 3p 2p 2s 4m 1m 1p 7p 8m 3c 2p 6m 1m 6s 9m 7m 5m 6p 7m 5m 1c 3m 3p 7p 3c 5s 8s 1c 7s 2s 2p 2m 4m 9m...

output:

49330101751/15939248518584875
544160045501/192992682900247428
4944118051151/1708687441192298600
14272852777/4980266365168215
244079458745/104349775513954302
1178845800113/347808183330273600
409704617233/124463414269524000
790856287777/260874438784885755
16282623809/5848263118189316
2143179701279/708...

result:

ok 10 lines

Test #8:

score: 10
Accepted
time: 505ms
memory: 6372kb

input:

10
126
5p 5c 3c 1p 3m 8m 4p 5p 3s 7p 3s 5p 6p 7p 4p 4s 3p 8p 8m 2m 1p 4m 1c 2s 9p 5c 4m 1s 8p 6s 9s 6c 5p 3s 7c 1m 4s 5c 7p 7c 5s 5m 2m 6s 7m 4s 8s 9m 2p 7m 5s 3c 9m 4p 4c 2s 9p 4p 6m 2s 3p 6m 1p 3m 5m 2c 2p 1s 1p 8p 3s 4c 1s 6s 6p 9m 9m 1c 4s 8s 9p 4m 7c 6c 5m 6s 7m 1m 2m 3p 1m 6c 3m 7s 1c 5s 9s 8s...

output:

1769364720488/459365261817235125
132486320564/47520544325920875
95007114903/33735175385867210
3834820426178/1378095785451705375
4207030689371/1378095785451705375
1995823601647/684548778482382000
10045994464373/3060335715568296000
3901375737747/1223890240316986000
145058089283/63083373958797390
49271...

result:

ok 10 lines

Test #9:

score: 10
Accepted
time: 532ms
memory: 6440kb

input:

10
125
4m 6s 3c 5m 1p 3s 1c 8s 1s 4c 5m 9s 8s 1s 3s 1m 6m 3m 9m 5s 1p 9p 6c 7m 3c 2p 3p 6c 2m 2m 2c 8p 3p 6p 9s 7s 1s 4m 7m 7p 2s 5s 3m 4s 5c 9s 3s 6c 2c 9m 7s 4p 5m 6s 1m 7p 6p 2p 3s 5p 2p 7m 6p 8p 2c 8s 5s 7p 6c 2s 8m 1s 8s 4s 6s 6s 2c 8p 8m 5p 1p 3c 3c 5c 3p 4p 1p 7m 5s 8p 6m 1c 2p 5c 6p 4p 5p 7s...

output:

3994538145151/1224974031512627000
164912958069/72057295971331000
4513127238533/1378095785451705375
36762818149/12709245430355940
5058554068093/1708687441192298600
8187159059951/2447780480633972000
105676567673/30597256007924650
1511235978388/516277772130874875
172118211457/55123831418068215
96726780...

result:

ok 10 lines

Test #10:

score: 10
Accepted
time: 642ms
memory: 6376kb

input:

10
136
7s 2p 1s 8m 9m 2c 9s 6p 7s 9s 4p 3p 4m 4p 7p 5p 4p 2c 3s 4m 1m 9p 4c 6c 2m 8s 3s 6s 6m 5m 1p 5s 8m 9p 2m 6p 6m 3s 1m 8s 4c 4m 7c 3c 3m 2p 5m 3p 1s 8p 6p 6m 2p 6s 7m 2p 3c 5s 3m 2s 6c 9m 8s 7c 2s 4p 8m 1s 6c 3m 2c 1p 1s 7c 5p 9m 3p 7s 4s 3m 9s 7p 9p 5m 6c 4s 5c 6s 1m 6m 1c 7m 8p 9s 1p 2m 3s 7s...

output:

2143179701279/708384171528036000
98667734899/31773113575889850
2268378791823/683474976476919440
1427183516417/476596703638347750
2143179701279/708384171528036000
1369334608447/423641514345198000
1427183516417/476596703638347750
98667734899/31773113575889850
2143179701279/708384171528036000
214317970...

result:

ok 10 lines