记录编号	234732	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-03-09 10:43:32	内存使用	0.50 MiB

#include<cstdio>
int ufs[10050];//ufs[0]\ufs[1]:0\1 ufs[i]:明文中第i-1个字符 
int find(int x){
	if(ufs[x]==x)return x;
	else return ufs[x]=find(ufs[x]);
}
void link(int a,int b){//如果存在0\1，放在b上。尚未保证检验后不矛盾 
//	printf("link(%d,%d)\n",a-1,b-1);
	ufs[find(a)]=find(b); 
}
char s1[10005],s2[10005];
int l1[10005],l2[10005];//l1[i]:s1[i]的密文对应的第一个字符在明文第几个字符 
int len[280];
struct node{
	int pos,next;
}lst[10005];int size=1;
int first[280];
void insert(char ch,int l){
	lst[size].pos=l;
	lst[size].next=first[ch];
	first[ch]=size++;
}

void merge(int a,int b,int l){
//	printf("merge(%d %d)",a,b);
	for(int i=0;i<l;++i){
		link(a+i+2,b+i+2);//a、b为从0开始的数组下标 
	}
}
int main(){
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	for(int i=0;i<10050;++i)ufs[i]=i;
	scanf("%s %s",s1,s2);
	int n;scanf("%d",&n);
	char buf[3];
	for(int i=1;i<=n;++i){
		scanf("%s",buf);
		scanf("%d",&len[buf[0]]);
	}
	len['0']=len['1']=1;
	int k;
	for(k=0;s1[k]!='\0';++k){
		l1[k+1]=l1[k]+len[s1[k]]; 
	}
	int orilen=l1[k];
	for(int i=0;s2[i]!='\0';++i){
		l2[i+1]=l2[i]+len[s2[i]]; 
//		printf("%d ",l2[i]);
	}
//	printf("\n");
	for(int i=0;s1[i]!='\0';++i){
		insert(s1[i],l1[i]);
	}
	for(int i=0;s2[i]!='\0';++i){
		insert(s2[i],l2[i]);
	}
	for(int i='a';i<='z';++i){
		int old=lst[first[i]].pos;
		for(int pt=lst[first[i]].next;pt;pt=lst[pt].next){
//			printf("pos%d\n",lst[pt].pos);
			merge(old,lst[pt].pos,len[i]);
		}
	}
	for(int i='0';i<='1';++i){
		for(int pt=first[i];pt;pt=lst[pt].next){
			if(i=='0'&&find(lst[pt].pos+2)!=1)link(lst[pt].pos+2,i-'0');//应传入从0开始的下标作为参数 
			else if(i=='1'&&find(lst[pt].pos+2)!=0)link(lst[pt].pos+2,i-'0');
			else{
				printf("0\n");
				fclose(stdin);fclose(stdout);
				return 0;
			}
		}
	}
	orilen+=2;
	int ans=0;
	for(int i=2;i<orilen;++i){
		
		if(ufs[i]==i){
			ans++;
//			printf("i%d ufs%d\n",i,ufs[i]);
		}
	}
	printf("%d",1<<ans);
	fclose(stdin);fclose(stdout);
	return 0;
}