比赛 期末考试0 评测结果 AWWWWWWWTT
题目名称 学姐的下午茶 最终得分 10
用户昵称 2_16鸡扒拌面 运行时间 6.622 s
代码语言 C++ 内存使用 3.81 MiB
提交时间 2026-02-07 12:22:55
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int N=25;
const int L=105;

int n;
string s[N];
ll ans=0;
int tq=0;

ll qp(ll a,ll b){
 ll r=1;
 while(b){
  if(b&1)r=r*a%MOD;
  a=a*a%MOD;
  b>>=1;
 }
 return r;
}

bool ok(int id,string&p){
 if(s[id].size()<p.size())return 0;
 for(int i=0;i<p.size();i++){
  if(s[id][i]!='?'&&s[id][i]!=p[i])return 0;
 }
 return 1;
}

int main(){
	freopen("lowtea.in","r",stdin);
    freopen("lowtea.out","w",stdout);
 cin>>n;
 for(int i=0;i<n;i++){
  cin>>s[i];
  for(char c:s[i])if(c=='?')tq++;
 }
 
 ans=qp(2,tq);
 
 set<string>ps;
 for(int i=0;i<n;i++){
  for(int l=1;l<=s[i].size();l++){
   ps.insert(s[i].substr(0,l));
  }
 }
 
 for(string p:ps){
  int m=p.size();
  vector<int>v;
  for(int i=0;i<n;i++){
   if(ok(i,p))v.push_back(i);
  }
  
  if(v.empty())continue;
  
  int k=v.size();
  ll cnt=0;
  
  for(int msk=1;msk<(1<<k);msk++){
   map<pair<int,int>,char>mp;
   bool cf=0;
   int fc=0;
   
   for(int i=0;i<k;i++){
    if(msk>>i&1){
     int id=v[i];
     for(int j=0;j<m;j++){
      if(s[id][j]=='?'){
       pair<int,int>pos={id,j};
       if(mp.count(pos)){
        if(mp[pos]!=p[j]){
         cf=1;
         break;
        }
       }else{
        mp[pos]=p[j];
        fc++;
       }
      }
     }
     if(cf)break;
    }
   }
   
   if(cf)continue;
   
   ll w=qp(2,tq-fc);
   int bt=__builtin_popcount(msk);
   if(bt&1){
    cnt=(cnt+w)%MOD;
   }else{
    cnt=(cnt-w+MOD)%MOD;
   }
  }
  
  ans=(ans+cnt)%MOD;
 }
 
 cout<<ans<<endl;
 return 0;
}