记录编号	243695	评测结果	AAAAAAAAAAAA
题目名称	[POI 1998] 单词等式	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2016-03-30 12:16:15	内存使用	0.92 MiB

#include<cstdio>
#include<cstring>
int len[280];
char s1[10005],s2[10005];
int ufs[10005];//ufs[0]stand for '0'.ufs[1] stand for '1'
//find(a)==find(b):原字符串a-2和b-2位置上字符相同 
bool flag;
int find(int x){
	return x==ufs[x]?x:ufs[x]=find(ufs[x]);
}
void link(int a,int b){
	int ra=find(a),rb=find(b);
	if(ra<rb)ra^=rb^=ra^=rb;
	if(ra==1&&rb==0)flag=false;
	ufs[ra]=rb;
} 
struct node{
	int pos,next;
}lst[50000];int tail=1;
int first[280];
int buf[50000];
void printpow(int a){
	int length=0;
	buf[0]=1;
	for(int i=1;i<=a;++i){
		for(int j=0;j<=length;++j){
			buf[j]*=2;
		}
		for(int j=0;j<=length;++j){
			if(buf[j]>=10000){
				buf[j+1]+=buf[j]/10000;
				buf[j]%=10000;
				if(j==length)length++;
			}
		}
	}
	printf("%d",buf[length]);
	for(int i=length-1;i>=0;--i)printf("%04d",buf[i]);
}
int main(){
	freopen("row.in","r",stdin);
	freopen("row.out","w",stdout);
	int t;scanf("%d",&t);
	while(t--){
		int k;scanf("%d",&k);
		for(int i=0;i<k;++i){
			scanf("%d",len+'a'+i);
		}
		flag=true;
		len['0']=len['1']=1;
		int len1,len2;
		int totlen=0;
		tail=1;
		memset(first,0,sizeof(first));
		scanf("%d%s%d%s",&len1,s1,&len2,s2);
		for(int i=0;i<len1;++i){
		/*	if(s1[i]<='1'){
				totlen++;
				continue;
			}*/
			lst[tail].pos=totlen;
			lst[tail].next=first[s1[i]];
			first[s1[i]]=tail++;	
			totlen+=len[s1[i]];
		}
		int totlen1=totlen;
		totlen=0;
		for(int i=0;i<len2;++i){
		/*	if(s2[i]<='1'){
				totlen++;continue;
			}*/
			lst[tail].pos=totlen;
			lst[tail].next=first[s2[i]];
			first[s2[i]]=tail++;	
			totlen+=len[s2[i]];
		}
		if(totlen1!=totlen)flag=false;
		totlen+=2;
		for(int i=0;i<totlen;++i)ufs[i]=i;
		for(int pt=first['0'];pt;pt=lst[pt].next){
			link(0,lst[pt].pos+2);
		}
		for(int pt=first['1'];pt;pt=lst[pt].next){
			link(1,lst[pt].pos+2);
		}
		for(int i=0;i<k;++i){
			int pt=first['a'+i],old=lst[pt].pos;
			for(pt=lst[pt].next;pt;pt=lst[pt].next){
				int now=lst[pt].pos;
				for(int j=0;j<len['a'+i];++j){
					link(old+j+2,now+j+2);
				}
			}
		}
		if(!flag){
			printf("0\n");
			continue;
		}
		int ans=0;
		for(int i=2;i<totlen;++i){
			if(ufs[i]==i&&ufs[i]>1)ans++;
		}
		printpow(ans);
		printf("\n");
	}
	fclose(stdin);fclose(stdout);
	return 0;
}