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