记录编号	104290	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-06-04 18:20:27	内存使用	0.34 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

string s1 , s2;
int sig[2]={2601,2602};
int data1 [ 2601 ] = { 0 } , data2 [ 2601 ] = { 0 };
int father [ 2601 + 1 ] = { 0 };
int word [ 26 ] = { 0 };
int ans = 1;
bool f [ 2602 ] = { 0 };

void In();
void Out();
void Union(int x,int y);
int Find(int x);

int main()
{
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	In();
	Out();
	return 0;
}

void In()
{
	char ch;
	int t = 0;
	cin >> s1 >> s2;
	cin >> t;
	while ( t -- )
	{
		cin >> ch;
		cin >> word [ ch - 'a' ];
	}
	for (int i = 0;i < s1.size();i ++ )
	{
		ch = s1[ i ];
		if (ch == '0' || ch == '1')
			data1 [ ++ data1 [ 0 ] ] = sig[ch-'0'];
		else
		{
			t = ch - 'a';
			for (int j = 1;j <= word [ t ];j ++ )
				data1 [ ++ data1 [ 0 ] ] = t * 100 + j;
		}
	}
	for (int i = 0;i < s2.size();i ++ )
	{
		ch = s2[ i ];
		if (ch == '0' || ch == '1')
			data2 [ ++ data2 [ 0 ] ] = sig[ch-'0'];
		else
		{
			t = ch - 'a';
			for (int j = 1;j <= word [ t ];j ++ )
				data2 [ ++ data2 [ 0 ] ] = t * 100 + j;
		}
	}
}

void Out()
{
	father [sig[0]]=sig[0];
	father [sig[1]]=sig[1];
	if ( data1 [ 0 ] != data2 [ 0 ])
	{
		cout << "0" << endl;
		return;
	}
	for ( int i = 1;i <= data1 [ 0 ];i ++ )
	{
		Union(data1 [ i ],data2 [ i ]);
	}
	for ( int i = 1;i <= data1 [ 0 ];i ++ )
	{
		int r = Find(data1 [ i ]);
		if ( r != sig[1] && r != sig[0] && ! f [ r ])
		{
			ans *= 2;
			f [ r ] = true;
		}
	}
	cout << ans << endl;
}

void Union(int x,int y)
{
	int r1 = Find(x);
	int r2 = Find(y);
	if (r1 == sig[0] && r2 == sig[1])
	{
		cout<<0<<endl;
		exit(0);
	}
	if (r1 == sig[1] && r2 == sig[0])
	{
		cout<<0<<endl;
		exit(0);
	}
	if ( r1 == r2) return ;
	if ( r1 > r2 ) father [ r2 ] = r1;
	else if ( r1 < r2 ) father [ r1 ] = r2;
}

int Find(int x)
{
	if ( father [ x ] == sig[0] || father[x] == sig[1]) return father[x];
	if ( father [ x ] == 0 || father [ x ] == x )
	{
		father [ x ] = x;
		return x;
	}
	father [ x ] = Find( father [ x ] );
	return father [ x ];
}