记录编号	47556	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	青阳	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-11-01 22:59:06	内存使用	2.05 MiB

/*
author: bluscy
date: 2012-10-29
*/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define MAXN 10000
int n;
char s1[MAXN + 1], s2[MAXN + 1];
int len[26], fs, l;
int sum[26], father[MAXN + 2];
int used[26], mark[MAXN + 2];

int num(char a, int b)
{
	return sum[a - 'a'] + b;
}

int getfather(int x)
{
	if(father[x] == x){
		return x;
	}
	return father[x] = getfather(father[x]);
}

int judge(int a, int b)
{
	int x1, x2;
	x1 = getfather(a);
	x2 = getfather(b);
	if(x1 != x2){
		father[x1] = x2;
	}
	return x2;
}

void init(void)
{
	int i, t, s;
	char c;
	freopen("encrypt.in", "r", stdin);
	freopen("encrypt.out", "w", stdout);
	gets(s1), gets(s2);
	scanf("%d", &n);
	for(i = 0; i < n; i++){
	      	do{
			scanf("%c", &c);
		}while(!(c >= 'a' && c <= 'z'));
		scanf("%d", &t);
		len[c - 'a'] = t;
		fs += t;
	}
	for(i = 0; s1[i] != '\0'; i++){
		if(isalpha(s1[i])){
			l += len[s1[i] - 'a'];
			used[s1[i] - 'a'] = 1;
		}else{
			l++;
		}
	}
	s = 0;
	for(i = 0; s2[i] != '\0'; i++){
		if(isalpha(s2[i])){
			s += len[s2[i] - 'a'];
			used[s2[i] - 'a'] = 1;
		}else{
			s++;
		}
	}
	if(s != l){
		printf("0\n");
		exit(0);
	}
	sum[0] = 0;
	for(i = 1; i < 26; i++){
		sum[i] = sum[i - 1] + len[i - 1];
	}
	for(i = 0; i < fs; i++){
		father[i] = i;
	}
	father[MAXN] = MAXN;
	father[MAXN + 1] = MAXN + 1;
}

void slove(void)
{
	int i, j;
	int p1, pp1, p2, pp2;
	int re = 0;
	char a, b;
	p1 = pp1 = 0;
	p2 = pp2 = 0;
	for(i = 0; i < l; i++){
		a = isdigit(s1[p1]);
		b = isdigit(s2[p2]);
		if(a && !b){
			judge(MAXN + s1[p1] - '0', num(s2[p2], pp2));
			p1++;
			if(pp2 == len[s2[p2] - 'a'] - 1){
				p2++, pp2 = 0;
			}else{
				pp2++;
			}
		}else if(!a && b){
			judge(MAXN + s2[p2] - '0', num(s1[p1], pp1));
			p2++;
			if(pp1 == len[s1[p1] - 'a'] - 1){
				p1++, pp1 = 0;
			}else{
				pp1++;
			}
		}else if(a && b){
			if(s1[p1] != s2[p2]){
				printf("0\n");
				exit(0);
			}
			p1++, p2++;
		}else{
			judge(num(s1[p1], pp1), num(s2[p2], pp2));
			if(pp1 == len[s1[p1] - 'a'] - 1){
				p1++, pp1 = 0;
			}else{
				pp1++;
			}
			if(pp2 == len[s2[p2] - 'a'] - 1){
				p2++, pp2 = 0;
			}else{
				pp2++;
			}
		}
	}
	if(getfather(MAXN) == getfather(MAXN + 1)){
		printf("0\n");
		exit(0);
	}
	mark[getfather(MAXN)] = 1;
	mark[getfather(MAXN + 1)] = 1;
	for(i = 0; i < 26; i++){
		if(used[i]){
			for(j = sum[i]; j < sum[i] + len[i]; j++){
				if(!mark[getfather(j)]){
					mark[getfather(j)] = 1;
					re++;
				}
			}
		}
	}
	long long ans = 1;
	printf("%lld\n", (long long)ans << (re));
}

int main(void)
{
	init();
	slove();
	return 0;
}