| 比赛 |
期末考试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;
}