记录编号	236167	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-03-13 00:07:12	内存使用	0.00 MiB

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;} 
struct Password{
	char a[10010],b[10010];
	int list[28];
	int F[28][101];
	bool v[10010];
	int p1[10010],p2[10010];
	int len1,len2;
	int ppt;
	Password(){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(p1,-1,sizeof(p1));memset(p2,-1,sizeof(p2));memset(v,0,sizeof(v));len1=0;len2=0;}
	bool doing(){
		in();
		if(!TJ()){
			
			puts("0");
			return 0;
		}
		judge();//printf(">>>>ppt=%d\n",ppt);
		return 1;
	}
	bool in(){
		int k;char c;
		scanf("%s %s %d",a+1,b+1,&k);
		for(int i=1;i<=k;i++){
			scanf(" %c",&c);
			scanf("%d",&list[c-'a']);
		}
	}
	bool TJ(){
		for(int i=1;a[i]!='\0';i++){
			if(a[i]=='1'||a[i]=='0'){
				p1[++len1]=a[i]-'0';
			}
			else {
				for(int j=1;j<=list[a[i]-'a'];j++){
					p1[++len1]=100*(a[i]-'a'+1)+j;
				}
			}
			//watch();
		}
		for(int i=1;b[i]!='\0';i++){
			if(b[i]=='1'||b[i]=='0'){
				p2[++len2]=b[i]-'0';
			}
			else {
				for(int j=1;j<=list[b[i]-'a'];j++){
					p2[++len2]=100*(b[i]-'a'+1)+j;
				}
			}
			//printf("b[%d]=%c",i,b[i]);
			//watch();
		}
		if(len1!=len2)return 0;
		return 1;
	}
	bool judge(){
		for(int i=0;i<=27;i++){
			for(int j=1;j<=100;j++){
				F[i][j]=i*100+j;
			}
		}
		int k,q;
		long long ans=1;
		for(int i=1;i<=len1;i++){
			k=find(p1[i]),q=find(p2[i]);
			if((k==1||k==0)&&(q==1||q==0)){
				//printf("i=%d k=%d q=%d\n",i,k,q);
				if(k!=q){puts("0");return 0;}
			}
			else Make(min(k,q),max(q,k));
		}
		for(int i=1;i<=len1;i++){
			k=find(p1[i]);
			if(k!=0&&k!=1){
				if(!v[k])ans<<=1;
				v[k]=1;
			}
			//printf(">>>>>>ans=%lld k=%d\n",ans,k);
		}
		printf("%lld",ans);
		return 1;
	}
	void Make(int i,int j){
		F[j/100][j%100]=i;
	}
	int find(int i){
		int k=i,j;
		while(F[i/100][i%100]!=i){
			i=F[i/100][i%100];
		}
		while(k!=i){
			j=F[k/100][k%100];
			F[k/100][k%100]=i;
			k=j;
		}
		return i;
	}
	void watch(){
		printf("\n>>>>>>>>>>>>>>>>>>WATCH<<<<<<<<<<<<<<<<<<<<<\n");
		for(int i=1;i<=len1;i++){printf("p1[i=%d]=%d\n",i,p1[i]);}printf("\n");
		for(int i=1;i<=len2;i++){printf("p2[i=%d]=%d\n",i,p2[i]);}printf("\n");
		printf("\n>>>>>>>>>>>>>>>>>>WATCH<<<<<<<<<<<<<<<<<<<<<\n");
	}
}arcv;
void *_=freopen("encrypt.in","r",stdin);
void *__=freopen("encrypt.out","w",stdout);
int a=arcv.doing();
int main(){;}