#4674. and

제목 설명 제목 설명 제목 설명 은 정수 대 A, B 의 개 수 를 구하 고 정수 대 A, B 의 개 수 를 만족 시 키 며 정수 대 A, B 의 개 수 를 만족 시 키 고 만족 시 킵 니 다.
a ≤ A ≤ b a\le A\le b a≤A≤b
c ≤ B ≤ d c\le B\le d c≤B≤d
A + B = A ⊕ B . A+B=A\oplus B. A+B=A⊕B.
그 중에서 8853 은 위치 에 따라 다른 것 을 나타 낸다.그 중 \ oplus 는 위치 에 따라 다 르 거나그 중에서 8853 은 위치 에 따라 다른 것 을 나타 낸다.
입력 형식 입력 형식 입력 형식 4 개의 바 이 너 리 정수 a, b, c, d 4 개의 바 이 너 리 정수 a, b, c, d 4 개의 바 이 너 리 정수 a, b, c, d
전도 0 이 있 을 수 있 으 나, 각 정수 의 자릿수 는 전도 0 이 있 을 수 있 으 나, 각 정수 의 자릿수 는 전도 0 이 있 을 수 있 으 나, 각 정수 의 자릿수 ≤ 1 0 7 \ leq 10 ^ 7 ≤ 107.
출력 형식 출력 형식 한 줄, 한 정수, 답 한 줄, 한 정수, 답 한 줄, 한 정수, 답 m o d * 8201; (1 0 9 + 7) mod \, (10 ^ 9 + 7) mod (109 + 7)
샘플 샘플 샘플 입력 1 샘플 입력 1 샘플 입력00011110011100111100001001000 1101111011100001000 11000000110010011011101 11000000110011011101 11000000110010011101 11000000110011101 1001100110011001100110011001100110000101100111111 10011001100100100101100111111 100110000100101100111111 샘플 출력 2 샘플 출력 2 620469990 620469990 620469990 620469990 620469990
출처 출처 l r e lre lre
난수 D P 난수 DP 난수 DP 폭력 토론 폭력 토론 게시판 게시판 게시판 게시판 게시판

#include
#define N 10000007
using namespace std;
const long long mod=1e9+7;
long long f[2][2][2][2],g[2][2][2][2];
char aa[N],bb[N],cc[N],dd[N];
int a[N],b[N],c[N],d[N];
long long work(int lt,int *x,int *y){
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    f[1][1][0][0]=1;
    for(int i=1;i<=lt;++i){
    	long long xuyu=0,xuyd=0,xdyu=0,xdyd=0;
    	//up     down     
    	for(int j=0;j<=1;++j){
    		for(int k=0;k<=1;++k){
    			if(j==1&&k==1)continue;
    			xuyu+=f[1][1][j][k];
    			xuyd+=f[1][0][j][k];
    			xdyu+=f[0][1][j][k];
    			xdyd+=f[0][0][j][k];
    		}
    	}
    	for(int j=0;j<=1;++j){
    		for(int k=0;k<=1;++k){
    			if(j==1&&k==1)continue;
    			g[0][0][j][k]+=xdyd;
    		}
    	}
    	
    	if(x[i]==1&&y[i]==1){
    		g[0][0][0][0]+=xuyu+xuyd+xdyu;
    		g[0][0][1][0]+=xdyu;
    		g[0][0][0][1]+=xuyd;
    		g[1][0][1][0]+=xuyu+xuyd;
    		g[0][1][0][1]+=xdyu+xuyu;
    	}
    	if(x[i]==1&&y[i]==0){
    		g[0][0][0][0]+=xuyd;
    		g[0][0][1][0]+=0;
    		g[0][0][0][1]+=xuyd;
    		g[1][0][1][0]+=xuyd;
    		g[0][1][0][0]+=xuyu+xdyu;
    		g[0][1][1][0]+=xdyu;
    		g[1][1][1][0]+=xuyu;
    	}
    	if(x[i]==0&&y[i]==1){
    		g[0][0][0][0]+=xdyu;
    		g[0][0][1][0]+=xdyu;
    		g[0][0][0][1]+=0;
    		g[1][0][0][0]+=xuyu+xuyd;
    		g[1][0][0][1]+=xuyd;
    		g[0][1][0][1]+=xdyu;
    		g[1][1][0][1]+=xuyu;
    	}
    	if(x[i]==0&&y[i]==0){
    	    g[0][0][0][0]+=0;
    	    g[1][0][0][0]+=xuyd;
    	    g[1][0][0][1]+=xuyd;
    	    g[0][1][0][0]+=xdyu;
    	    g[0][1][1][0]+=xdyu;
    	    g[1][1][0][0]+=xuyu;
    	}
    	
    	for(int j=0;j<=1;j++){
    		for(int k=0;k<=1;++k){
    			for(int h=0;h<=1;++h){
    				for(int l=0;l<=1;++l){
    					if(h==1&&l==1)continue;
    					f[j][k][h][l]=g[j][k][h][l]%mod;
    	memset(g,0,sizeof(g));
    }
    long long ans=0;
    for(int j=0;j<=1;j++){
    	for(int k=0;k<=1;++k){
    		for(int h=0;h<=1;++h){
        		for(int l=0;l<=1;++l){
        			if(h==1&&l==1)continue;
    				ans=(ans+f[j][k][h][l])%mod;
    			}
    		}
    	}
    } 
    return ans;
}
    		
		
    		
int main(){
    scanf("%s%s%s%s",aa,bb,cc,dd);
	int la=strlen(aa),lb=strlen(bb),lc=strlen(cc),ld=strlen(dd),lt=max(max(la,lb),max(lc,ld));
	for(int i=1;i<=lt;++i){
		if(la>=lt-i+1)a[i]=aa[i-(lt-la+1)]-'0';
		if(lb>=lt-i+1)b[i]=bb[i-(lt-lb+1)]-'0';
		if(lc>=lt-i+1)c[i]=cc[i-(lt-lc+1)]-'0';
		if(ld>=lt-i+1)d[i]=dd[i-(lt-ld+1)]-'0';
	}
	long long ans=0;
	int flaga=0,flagc=0;
	ans=work(lt,b,d);
	for(int i=lt;i>=1;--i){
		if(a[i]==1){
			a[i]=0;flaga=1;break;
		}else{
			a[i]=1;
		}
	}
	for(int i=lt;i>=1;--i){
		if(c[i]==1){
			c[i]=0;flagc=1;break;
		}else{
			c[i]=1;
		}
	}
	if(flaga&&flagc){
		ans=(ans-work(lt,a,d)-work(lt,b,c)+work(lt,a,c))%mod;
	}
	if(flaga&&flagc==0){
		ans=(ans-work(lt,a,d))%mod;
	}
	if(flaga==0&&flagc){
		ans=(ans-work(lt,b,c))%mod;
	}
	printf("%lld
",(ans+mod)%mod);
	return 0;
}
/*
00
00
00
10
*/