比赛 期末考试0 评测结果 AWWWWWWWWW
题目名称 学姐的下午茶 最终得分 10
用户昵称 彭欣越 运行时间 0.032 s
代码语言 C++ 内存使用 3.74 MiB
提交时间 2026-02-07 11:59:04
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25,M=110,mod=1e9+7;
int n,sum,t,mx,mk[N][N],p[N][N],a[N][M],v0[N],v1[N];
ll ans,res,qp=1;
string s[N];
ll qpow (ll x,int k) {
    ll sum=1;
    while (k) {
        if (k&1) {
            sum*=x;
            sum%=mod; 
        }
        x*=x;
        x%=mod;
        k>>=1;
    }
    return sum;
}
int main () {
    freopen("lowtea.in","r",stdin);
    freopen("lowtea.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> s[i];
        for (int j=0;j<s[i].size();j++) {
            a[i][j]=a[i][j-1];
            if (s[i][j]=='?') {
                a[i][j]++;
                t++;
            }
        }
        int len=s[i].size();
        sum+=len;
        mx=max(mx,len);
    }
    ans=sum+1;
    for (int i=1;i<=t;i++) qp=qp*2%mod;
    ans=ans*qp%mod;
    //cout << ans <<' '<< qp <<endl;
    for (int i=0;i<mx;i++) {
        memset(v0,0,sizeof(v0));
        memset(v1,0,sizeof(v1));
        int jsq=0;
        for (int j=1;j<=n;j++) {
            for (int k=j+1;k<=n;k++) {
                if (mk[j][k]||i>=s[j].size()||i>=s[k].size()) continue;
                if (s[j][i]==s[k][i]) {
                    if (s[j][i]=='?') {
                        p[j][k]++;
                        //jsq++;
                        if (v0[j]&&v0[k]) {
                            if (v1[j]&&v1[k]) continue;
                            //v1[j]=v1[k]=1;
                            res+=qpow(2,t-a[j][i]-a[k][i]+p[j][k]-jsq)/2;
                        }else{
                            //v0[j]=v0[j]=1;
                            if (v1[j]&&v1[k]) res+=qpow(2,t-a[j][i]-a[k][i]+p[j][k]-jsq)/2;
                            res+=qpow(2,t-a[j][i]-a[k][i]+p[j][k]-jsq);
                            //v1[j]=v1[k]=1;
                        }
                        //cout << res <<endl;
                        continue;
                    }
                }else{
                    if (s[j][i]!='?'&&s[k][i]!='?') {
                        mk[j][k]=1;
                        continue;
                    }
                }
                ll op=qpow(2,t-a[j][i]-a[k][i]+p[j][k]-jsq);
                if (!jsq) {
                    if (s[j][i]=='0'||s[k][i]=='0') {
                        if (!v0[j]||!v0[k]) res+=op;
                        v0[j]=v0[k]=1; 
                    }else{
                        if (!v1[j]||!v1[k]) res+=op;                                         
                        v1[j]=v1[k]=1;
                    }
                }else{
                    res+=op;
                }
                res%=mod;
                //cout << res <<' '<< j <<' '<< k <<' '<< i <<endl;
            }
            if (s[j][i]=='?') jsq++;
        }
    }
    cout << (ans-res+mod)%mod <<endl;
    return 0;
}