记录编号	81804	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	Mongo	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2013-11-18 13:52:33	内存使用	0.50 MiB

//#define lgg
#ifdef lgg
#include <iostream>
#endif
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void read(); bool inti(); bool make(); bool brush(int);
#ifdef lgg
void show(); void dfs(int r);
#endif

ifstream in("encrypt.in"); ofstream out("encrypt.out");
vector<unsigned> g[10001];
typedef vector<unsigned>::iterator it;
unsigned N, S, ch[26], beg[26], m[10001], sum(1);
string ori1, ori2;
enum Co{white, gray, black}co[10001];
int main()
{
	read();
	if(!inti())
	{
		out << 0 << endl; return 0;
	}
	#ifdef lgg
	show();
	#endif
	if(!make())
	{
		out << 0 << endl; return 0;
	}
	out << sum << endl;
	return 0;
}
#ifdef lgg
void show()
{
	for(int i(1); i<S; ++i)
	{
		cout << "点" << i << "为" << m[i] << "通向点：";
		dfs(i);
		cout << endl;
		for(int j(1); j<S; ++j)
			co[j]=white;
	}
	return;
}
void dfs(int r)
{
	co[r]=gray;
	cout << r << ' ';
	for(it i=g[r].begin(); i!=g[r].end(); ++i)
		if(co[*i]==white)
			dfs(*i);
	co[r]=black;
	return;
}
#endif
inline void read()
{
	in >> ori1 >> ori2 >> N;
	for(unsigned i(1); i<=N; ++i)
	{
		char t; in >> t;
		in >> ch[t-'a'];
	}
	return;
}
inline bool inti()
{
	unsigned a=ori1.size(), b=ori2.size();
	unsigned now(1);
	for(unsigned i(0); i<a; ++i)
	{
		unsigned adv(1);//表示该单位前进几步
		if(ori1[i]>='a' && ori1[i]<='z')
		{
			adv=ch[ori1[i]-'a'];
			if(beg[ori1[i]-'a']==0)
				beg[ori1[i]-'a']=now;
			else
				for(unsigned t(0); t<adv; ++t)
				{
					g[now+t].push_back(beg[ori1[i]-'a']+t);
					g[beg[ori1[i]-'a']+t].push_back(now+t);
				}
		}
		else
			m[now]=ori1[i]-'0'+1;
		now+=adv;
	}
	S=now;
	now=1;
	for(unsigned i(0); i<b; ++i)
	{
		unsigned adv(1);//表示该单位前进几步
		if(ori2[i]>='a' && ori2[i]<='z')
		{
			adv=ch[ori2[i]-'a'];
			if(beg[ori2[i]-'a']==0)
				beg[ori2[i]-'a']=now;
			else
				for(unsigned t(0); t<adv; ++t)
				{
					g[now+t].push_back(beg[ori2[i]-'a']+t);
					g[beg[ori2[i]-'a']+t].push_back(now+t);
				}
		}
		else
		{
			if(m[now]==0)
				m[now]=ori2[i]-'0'+1;
			else if(m[now]!=ori2[i]-'0'+1)
				return 0;
		}
		now+=adv;
	}
	if(now!=S)
		return 0;
	return 1;
}
bool make()
{
	while(1)
	{
		bool isok(0);
		for(unsigned i(1); i<S; ++i)
			if(co[i]==white && m[i]!=0)
			{
				if(!brush(i))
					return 0;
				else
				{
					isok=1;
					break;
				}
			}
		if(isok==0)break;
	}
	while(1)
	{
		bool isok(0);
		for(unsigned i(1); i<S; ++i)
			if(m[i]==0)
			{
				if(sum==0)
					sum=1;
				else
					sum<<=1;
				m[i]=4;
				brush(i);
			}
		if(isok==0)break;
	}
	return 1;
}
bool brush(int r)
{
	co[r]=gray;
	for(it i=g[r].begin(); i!=g[r].end(); ++i)
		if(co[*i]==white)
		{
			if(m[*i]!=0)
				if(m[*i]!=m[r])
					return 0;
			m[*i]=m[r];
			if(!brush(*i))
				return 0;
		}
	return 1;
}