求大佬帮忙看看代码:
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int len=1<<16;
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline void sub(int &x,int y){x=(x<y?x-y+mod:x-y);}
inline void fwtor(int *f,int flg){
for(int i=2;i<=len;i<<=1)
for(int j=0,p=i/2;j<len;j+=i)
for(int k=j;k<j+p;k++)
if(flg)add(f[k+p],f[k]);
else sub(f[k+p],f[k]);
}
inline void fwtand(int *f,int flg){
//puts("in fwtand");
for(int i=2;i<=len;i<<=1)
for(int j=0,p=i/2;j<len;j+=i)
for(int k=j;k<j+p;k++)
if(flg)add(f[k],f[k+p]);
else sub(f[k],f[k+p]);
//puts("out fwtand");
}
int n,m,f[500][len],c[16],ans,tot,rt,tmp[len];string s;
inline int solve(int l,int r){
int h=++tot;
//printf("%d %d\n",l,r);
//system("pause");
if(l==r){
int id;
if(s[l]=='?')id=9;
else if(s[l]>='A'&&s[l]<='D')id=s[l]-'A'+1;
else id=s[l]-'a'+5;
for(int i=0;i<len;i++)f[h][i]=f[id][i];
return h;
}int pos,top=0;
for(int i=l;i<=r;i++){
if(s[i]=='(')++top;
else if(s[i]==')')--top;
if(top==0&&s[i]==')'){pos=i+1;break;}
}int ls=solve(l+1,pos-2),rs=solve(pos+2,r-1);//puts("out");
if(s[pos]=='|'){//puts("in or");
fwtor(f[ls],1);fwtor(f[rs],1);
for(int i=0;i<len;i++)f[h][i]=1ll*f[ls][i]*f[rs][i]%mod;
fwtor(f[h],0);
}else if(s[pos]=='&'){//puts("in and");
fwtand(f[ls],1);fwtand(f[rs],1);
for(int i=0;i<len;i++)f[h][i]=1ll*f[ls][i]*f[rs][i]%mod;
fwtand(f[h],0);
}else{
fwtor(f[ls],1);fwtor(f[rs],1);
for(int i=0;i<len;i++)f[h][i]=1ll*f[ls][i]*f[rs][i]%mod;
fwtor(f[h],0);fwtor(f[ls],0);fwtor(f[rs],0);
fwtand(f[ls],1);fwtand(f[rs],1);
for(int i=0;i<len;i++)tmp[i]=1ll*f[ls][i]*f[rs][i]%mod;
fwtand(tmp,0);
for(int i=0;i<len;i++)add(f[h][i],tmp[i]);
}return h;
}
int main(){
cin>>s;n=s.size();
for(int i=0;i<4;i++){
int res=0;
for(int j=0;j<16;j++)
res=res*2+(j>>i&1);
f[i+1][res]=f[i+5][(len-1)^res]=1;
f[9][res]++;f[9][(len-1)^res]++;
}tot=9;
rt=solve(0,n-1);//puts("out");
memset(c,-1,sizeof(c));
m=read();
for(int i=1;i<=m;i++){
int res=0;
for(int j=0;j<4;j++)
res|=read()<<j;
c[res]=read();
}
for(int i=0;i<len;i++){
int flg=1;
for(int j=0;j<16;j++)
if(c[j]!=-1&&((i>>j&1)!=c[j]))flg=0;
if(flg)add(ans,f[rt][i]);
}printf("%d\n",ans);
return 0;
}
有一组错误数据:
((((((d)?(?))|((((B)|(?))?(?))?(?)))?(?))&(a))?((D)?((A)&(?))))?(((?)?(?))?((((?)?(?))?((?)?(?)))?((?)?(?))))
12
0 1 1 1 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0
1 1 0 0 0
0 0 1 0 0
1 1 1 1 0
1 0 1 0 0
0 1 0 1 0
0 0 1 1 0
0 1 0 0 0
1 1 0 1 0
答案为:
13407699
球球了,拜谢拜谢