记录编号	47585	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-11-02 10:41:16	内存使用	0.42 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
using namespace std;

char ch[30];
int len[30],na[10010],nb[10010],dad[3000],siz[3000];
bool used[3000];
stack<int> sta;

int findroot(int a)
{
	while (dad[a]!=-1)
	{
		sta.push(a);
		a=dad[a];
	}
	while (!sta.empty())
	{
		dad[sta.top()]=a;
		sta.pop();
	}
	return(a);
}

void combine(int a,int b)
{
	a=findroot(a);
	b=findroot(b);
	if (a<=1)
	{
		siz[a]+=siz[b];
		dad[b]=a;
		return;
	}
	if (b<=1)
	{
		siz[b]+=siz[a];
		dad[a]=b;
		return;
	}
	if (siz[a]>siz[b])
	{
		siz[a]+=siz[b];
		dad[b]=a;
	}
	else
	{
		siz[b]+=siz[a];
		dad[a]=b;
	}
}

int main(void)
{
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	int i,j,k,la,lb,n,nla,nlb,temp,temp2,total=0;
	string a,b;
	cin>>a>>b;
	la=a.length();
	lb=b.length();
	cin>>n;
	for (i=1;i<=n;i++)
		cin>>ch[i]>>len[i];
	nla=0;
	nlb=0;
	for (i=0;i<la;i++)
	{
		if (a[i]=='0'||a[i]=='1')
		{
			na[nla++]=a[i]-'0';
		}
		else
		{
			for (j=1;j<=n;j++)
			{
				if (a[i]==ch[j])
				{
					for (k=1;k<=len[j];k++)
						na[nla++]=100*(a[i]-'a'+1)+k-1;
					break;
				}
			}
		}
	}
	for (i=0;i<lb;i++)
	{
		if (b[i]=='0'||b[i]=='1')
		{
			nb[nlb++]=b[i]-'0';
		}
		else
		{
			for (j=1;j<=n;j++)
			{
				if (b[i]==ch[j])
				{
					for (k=1;k<=len[j];k++)
						nb[nlb++]=100*(b[i]-'a'+1)+k-1;
					break;
				}
			}
		}
	}
	for (i=0;i<3000;i++)
	{
		dad[i]=-1;
		siz[i]=1;
	}
	for (i=0;i<nla;i++)
	{
		temp=findroot(na[i]);
		temp2=findroot(nb[i]);
		if (temp!=temp2)
		{
			if ((temp==0&&temp2==1)||(temp==1&&temp2==0))
			{
				cout<<"0\n";
				return(0);
			}
			combine(na[i],nb[i]);
		}
	}
	for (i=0;i<nla;i++)
	{
		temp=findroot(na[i]);
		if (temp>1)
			used[temp]=true;
	}
	for (i=2;i<3000;i++)
		if (used[i])
			total++;
	cout<<(1<<total)<<endl;
	return(0);
}