题解：P13028 [GCJ 2021 #1A] Hacked Exam

· · 题解

前言

小清新组合计数题，但是代码写的太史了有点难受。

Solution

首先 N\le 2 的情形是简单的，请读者自行思考。

这里直接考虑 N=3。由于 T 比较大，显然我们需要一个单次 O(Q^3) 的做法。

一列大概有 8 个状态，然后 FFT 和 TTF 是本质相同的，于是一列只有 4 个不同状态，除去三个字符都相同的情况，只有 FFT，FTF，TFF 三种本质不同的状态，表示是否取出现次数较少的那个字符，设它们各有 c_1,c_2,c_3 个，三个字符相同的有 c_4 个，我们直接枚举 i\le c_1,j\le c_2,k\le c_3 即可，然后在 a_1-i=a_2-j=a_3-k 的前提下把合法方案数 \binom{c_1}{i}\binom{c_2}{j}\binom{c_3}{k}\binom{c_4}{a_1-i} 加进 sum 中。算每一位 T 和 F 的出现次数也是简单的，在总方案的基础上改动一下即可，然后取较大值加进 ans 里，最后的答案就是 \frac{ans}{sum}。

时间复杂度应该是 O(TQ^3) 的，实际上只跑了 71ms。

还是晒一下代码把，不喜勿喷。

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ld long double
#define ull unsigned long long
#define lll __int128
#define N 500010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mk make_pair
#define pb push_back
#define pii pair<ll,ll>
#define pque priority_queue
#define fi first
#define se second

using namespace std;
lll C[130][130];
char s[3][210];
int T,n,m,a[3];

ll read(){
    ll 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*10+ch-'0';ch=getchar();}
    return x*f;
}
void sc(lll x){
    if(x>=10) sc(x/10);
    int p=x%10;
    cout<<p;
}
lll gcd(lll x,lll y){
    if(!y) return x;
    return gcd(y,x%y);
}
void fenshu(lll x,lll y){
    lll d=gcd(x,y);
    x/=d,y/=d;
    cout<<' ';
    sc(x);
    cout<<"/";
    sc(y);
    cout<<endl;
}
lll C1(int u,int v){
    if(u<0 || v<0 || u<v) return 0;
    return C[u][v];
}
lll g[4][2];
char ans1[210];
void sol(int id){
    memset(g,0,sizeof(g));
    n=read(),m=read();
    For(i,0,n-1){
        cin>>(s[i]+1);
        a[i]=read();
    }
    printf("Case #%d: ",id);
    if(n==1){
        For(i,1,m){
            if(a[0]*2>=m){
                if(s[0][i]=='T') printf("T");
                else printf("F");
            }else{
                if(s[0][i]=='F') printf("T");
                else printf("F");
            }
        }
        fenshu(max(a[0],m-a[0]),1);
        return;
    }
    lll sum=0,ans=0;
    if(n==2){
        int c1=0,c2=0;
        For(i,1,m){
            if(s[0][i]==s[1][i]) c2++;
            else c1++;
        }
        For(i,0,c1){
            int f1=i,f2=c1-i;
            if(a[0]-f1==a[1]-f2 && a[0]-f1<=c2 && a[0]-f1>=0){
                sum+=C1(c1,i)*C1(c2,a[0]-f1);
                g[0][0]+=C1(c1-1,i-1)*C1(c2,a[0]-f1);
                g[0][1]+=C1(c1-1,i)*C1(c2,a[0]-f1);
                g[1][0]+=C1(c1,i)*C1(c2-1,a[0]-f1-1);
                g[1][1]+=C1(c1,i)*C1(c2-1,a[0]-f1);
            }
        }
        For(i,1,m){
            if(s[0][i]==s[1][i]) ans+=max(g[1][0],g[1][1]);
            else ans+=max(g[0][0],g[0][1]);
        }
        For(i,1,m){
            if(s[0][i]==s[1][i]){
                if(g[1][0]>=g[1][1]){
                    if(s[0][i]=='T') printf("T");
                    else printf("F");
                }else{
                    if(s[0][i]=='F') printf("T");
                    else printf("F");
                }
            }else{
                if(g[0][0]>=g[0][1]){
                    if(s[0][i]=='T') printf("T");
                    else printf("F");
                }else{
                    if(s[0][i]=='F') printf("T");
                    else printf("F");
                }
            }
        }
        fenshu(ans,sum);
        return;
    }
    int c1=0,c2=0,c3=0,c4=0;
    For(i,1,m){
        if(s[0][i]!=s[1][i] && s[0][i]!=s[2][i]) c1++;
        else if(s[1][i]!=s[0][i] && s[1][i]!=s[2][i]) c2++;
        else if(s[2][i]!=s[1][i] && s[0][i]!=s[2][i]) c3++;
        else c4++;
    }
    For(i,0,c1){
        For(j,0,c2){
            For(k,0,c3){
                int f1=i+c2-j+c3-k,f2=j+c1-i+c3-k,f3=k+c1-i+c2-j;
                if(a[0]-f1==a[1]-f2 && a[1]-f2==a[2]-f3 && a[0]-f1<=c4){
                    sum+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
                    g[0][0]+=C1(c1-1,i-1)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
                    g[0][1]+=C1(c1-1,i)*C1(c2,j)*C1(c3,k)*C1(c4,a[0]-f1);
                    g[1][0]+=C1(c1,i)*C1(c2-1,j-1)*C1(c3,k)*C1(c4,a[0]-f1);
                    g[1][1]+=C1(c1,i)*C1(c2-1,j)*C1(c3,k)*C1(c4,a[0]-f1);
                    g[2][0]+=C1(c1,i)*C1(c2,j)*C1(c3-1,k-1)*C1(c4,a[0]-f1);
                    g[2][1]+=C1(c1,i)*C1(c2,j)*C1(c3-1,k)*C1(c4,a[0]-f1);
                    g[3][0]+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4-1,a[0]-f1-1);
                    g[3][1]+=C1(c1,i)*C1(c2,j)*C1(c3,k)*C1(c4-1,a[0]-f1);
                }
            }
        }
    }
    For(i,1,m){
        if(s[0][i]!=s[1][i] && s[0][i]!=s[2][i]){
            ans+=max(g[0][0],g[0][1]);
            if(g[0][0]>=g[0][1]){
                if(s[0][i]=='T') printf("T");
                else printf("F");
            }else{
                if(s[0][i]=='F') printf("T");
                else printf("F");
            }
        }else if(s[1][i]!=s[0][i] && s[1][i]!=s[2][i]){
            ans+=max(g[1][0],g[1][1]);
            if(g[1][0]>=g[1][1]){
                if(s[1][i]=='T') printf("T");
                else printf("F");
            }else{
                if(s[1][i]=='F') printf("T");
                else printf("F");
            }
        }else if(s[2][i]!=s[1][i] && s[0][i]!=s[2][i]){
            ans+=max(g[2][0],g[2][1]);
            if(g[2][0]>=g[2][1]){
                if(s[2][i]=='T') printf("T");
                else printf("F");
            }else{
                if(s[2][i]=='F') printf("T");
                else printf("F");
            }
        }else{
            ans+=max(g[3][0],g[3][1]);
            if(g[3][0]>=g[3][1]){
                if(s[0][i]=='T') printf("T");
                else printf("F");
            }else{
                if(s[0][i]=='F') printf("T");
                else printf("F");
            }
        }
    }
    fenshu(ans,sum);
}

int main()
{
    //freopen("mex.in","r",stdin);
    //freopen("mex.out","w",stdout);
    For(i,0,129){
        C[i][0]=1;
        For(j,1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    T=read();
    For(i,1,T) sol(i);
    return 0;
}
/*

*/