Description
计算给定范围内有多少种输入可以使输出为1。 我们假设3 < n < 100, 3 < m < 3000，而且网络中的门是用1到m之间的数任意编号的。Input
文件第一行包含三个整数，分别表示输入的个数，门的个数，连接到输出的门的编号。以下的m行描述网络中的连接情况。第I行表示第I个门的两个输入，两个输入为范围[-n,m]之间的一个整数。如果输入是网络的第k个输入，则连接的描述是一个整数－k，如果输入是第j个门，则连接的描述是一个整数j。以下两行各有一个n位二进制串，表示输入的上限和下限。
Output
包含一个整数，表示给定范围内有多少种输入可以使输出为1。
由异或的性质，拓扑排序并处理出最终输出等于哪些输入异或起来，于是转成区间内有几个二进制数和指定数的按位与有奇数个1，可以数位dp
#include<cstdio>
#include<bitset>
typedef unsigned long long u64;
int n,m,o;
int es[],enx[],e0[],deg[],q[],ql=,qr=,ep=;
std::bitset<>st[];
int S[];
char l[],r[];
void ae(int a,int b){
es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;
++deg[b];
}
struct num{
u64 a,b;
num(u64 _a,u64 _b):a(_a),b(_b){};
num(u64 _a=):a(),b(_a){}
void print(){
int ss[],sp=;
u64 v1=a>>,v2=a&0xffffffffll;
u64 v3=b>>,v4=b&0xffffffffll;
while(v1|v2|v3|v4){
v2+=v1%<<;v1/=;
v3+=v2%<<;v2/=;
v4+=v3%<<;v3/=;
ss[sp++]=v4%;v4/=;
}
if(!sp)putchar('');
while(sp)putchar(''+ss[--sp]);
}
};
num operator+(num x,num y){
u64 c=x.b+y.b;
return num(x.a+y.a+(c<x.b),x.b+y.b);
}
num operator-(num x,num y){
return num(x.a-y.a-(x.b<y.b),x.b-y.b);
}
num f[][][];
void pre(){
f[n+][][]=;
for(int i=n;i;--i){
f[i][][]=f[i][][S[i]]=f[i+][][]+f[i+][][];
f[i][][]=f[i][][S[i]^]=f[i+][][]+f[i+][][];
}
}
num cal(char*s,bool e){
for(int i=;i<=n;++i)s[i]-='';
int d=;
num ans=;
for(int i=;i<=n;++i){
if(s[i])ans=ans+f[i][][d^];
if(S[i])d^=s[i];
}
if(e){
int d=;
for(int i=;i<=n;++i)if(S[i])d^=s[i];
ans=ans+d;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&o);
for(int i=,a,b;i<=m;++i){
scanf("%d%d",&a,&b);
if(a<)st[i].flip(-a);
else ae(a,i);
if(b<)st[i].flip(-b);
else ae(b,i);
}
for(int i=;i<=m;++i)if(!deg[i])q[++qr]=i;
while(ql!=qr){
int w=q[++ql];
for(int i=e0[w];i;i=enx[i]){
int u=es[i];
st[u]^=st[w];
if(!--deg[u])q[++qr]=u;
}
}
for(int i=;i<=n;++i)S[i]=st[o][i];
scanf("%s%s",l+,r+);
pre();
(cal(r,)-cal(l,)).print();
return ;
}