记录编号	56708	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2013-04-02 17:16:37	内存使用	0.44 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int SIZEL=10001;//明文最大长度
int s1[SIZEL]={0},s2[SIZEL]={0};//存放两段处理过的密码
//规则是Hash:"第k个字符temp"=(temp-'a'+1)*100+k,这里k是从0开始算的
int pl;//明文的长度
const int SIZEH=3000;//Hash的最大长度
int father[SIZEH]={0};//每个点的节点
class ROOT{
public:
	int size;
	bool doom;//是否有了固定的值(0/1)不要吐槽翻译......
	int data;//0或1
};
ROOT root[SIZEH];
int findgra(int x){
	if(father[x]==-1) return x;
	else return findgra(father[x]);
}
bool merger(int a,int b){//a,b两个集合合并
	if(root[a].size<=root[b].size){//a合到b里
		father[a]=b;
		root[b].size+=root[a].size,root[a].size=0;
		if(root[b].doom){//b已经有定值了
			if(root[a].doom&&root[a].data!=root[b].data) return false;
		}
		else root[b].doom=root[a].doom,root[b].data=root[a].data;
	}
	else{//b合到a里
		father[b]=a;
		root[a].size+=root[b].size,root[b].size=0;
		if(root[a].doom){
			if(root[b].doom&&root[b].data!=root[a].data) return false;
		}
		else root[a].doom=root[b].doom,root[a].data=root[b].data;
	}
	return true;
}
bool match(void){
	int i,temp;
	for(i=0;i<pl;i++){
		if(s1[i]==0||s1[i]==1){//s1是0或1
			if(s2[i]==0||s2[i]==1) {if(s1[i]!=s2[i]) return false;}//确定的不同,失配
			else{
				temp=findgra(s2[i]);
				if(root[temp].doom) {if(root[temp].data!=s1[i]) return false;}
				else root[temp].doom=true,root[temp].data=s1[i];
			}
		}
		else{
			if(s2[i]==0||s2[i]==1){
				temp=findgra(s1[i]);
				if(root[temp].doom) {if(root[temp].data!=s2[i]) return false;}
				else root[temp].doom=true,root[temp].data=s2[i];
			}
			else{
				int gra1=findgra(s1[i]),gra2=findgra(s2[i]);
				if(gra1!=gra2){
					if(!merger(gra1,gra2)) return false;
				}
			}
		}
	}
	return true;
}
int n;//密码个数
int expsum[30]={0};//每个密码对应几个字符
bool used[SIZEH]={0};
bool read(void){
	string str1,str2;//两段原始文本
	cin>>str1>>str2;
	scanf("%d",&n);
	int i,j,p,temp;
	char ch;
	for(i=0;i<n;i++){
		cin>>ch,cin>>expsum[ch-'a'];
		temp=100*(ch-'a'+1);
		for(j=0;j<expsum[ch-'a'];j++){
			father[temp+j]=-1;
			root[temp+j].size=1;
			root[temp+j].doom=false;
			root[temp+j].data=-1;
		}
	}
	p=0;
	for(i=0;i<(int)str1.size();i++){
		if(str1[i]=='0'||str1[i]=='1') s1[p++]=str1[i]-'0';//0或1
		else{//把这个扩展出去
			temp=(str1[i]-'a'+1)*100;
			for(j=0;j<expsum[str1[i]-'a'];j++) s1[p++]=temp+j,used[temp+j]=true;
		}
	}
	pl=p;
	p=0;
	for(i=0;i<(int)str2.size();i++){
		if(str2[i]=='0'||str2[i]=='1') s2[p++]=str2[i]-'0';//0或1
		else{//把这个扩展出去
			temp=(str2[i]-'a'+1)*100;
			for(j=0;j<expsum[str2[i]-'a'];j++) s2[p++]=temp+j,used[temp+j]=true;
		}
	}
	if(p!=pl) return false;//两个长度不一样,失配
	return true;
}
void write(void){
	int sum=0;
	int i,j,temp;
	for(i=0;i<26;i++){
		if(expsum[i]>0){
			temp=100*(i+1);
			for(j=0;j<expsum[i];j++){
				if(used[temp+j]&&root[temp+j].size>0&&!root[temp+j].doom) sum++;
			}
		}
	}
	cout<<(1<<sum)<<endl;
}
int main(){
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	bool flag;
	flag=read();//在这里读数据
	if(!flag) goto END;//失配了就直接0
	flag=match();
	if(!flag) goto END;
	write();
	return 0;
	END:;
	printf("0\n");
	return 0;
}