记录编号	577518	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-11-07 22:15:01	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
int n, cnt = 1, len1, len2, ans, len[110], fa[10010], w[110][110];
string s1, s2;
vector<int> a1, a2;
bool vis[10010];
int find(int x) {
	if(fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}
int main() {
	freopen("encrypt.in", "r", stdin);
	freopen("encrypt.out", "w", stdout);
	cin >> s1 >> s2 >> n;
	len1 = s1.length();
	len2 = s2.length();
	for(int i = 1; i <= n; i ++) {
		char c;
		cin >> c;
		cin >> len[c - 'a'];
		for(int j = 1; j <= len[c - 'a']; j ++) {
			w[c - 'a'][j] = ++ cnt;
		}
	}
	for(int i = 0; i < len1; i ++) {
		if(s1[i] == '0' || s1[i] == '1') {
			a1.push_back(s1[i] - '0');
		}
		else {
			for(int j = 1; j <= len[s1[i] - 'a']; j ++) {
				vis[w[s1[i] - 'a'][j]] = 1;
				a1.push_back(w[s1[i] - 'a'][j]);
			}
		}
	}
	len1 = a1.size();
	for(int i = 0; i < len2; i ++) {
		if(s2[i] == '0' || s2[i] == '1') {
			a2.push_back(s2[i] - '0');
		}
		else {
			for(int j = 1; j <= len[s2[i] - 'a']; j ++) {
				vis[w[s2[i] - 'a'][j]] = 1;
				a2.push_back(w[s2[i] - 'a'][j]);
			}
		}
	}
	len2 = a2.size();
	if(len1 != len2) {
		cout << 0;
		return 0;
	}
	int x,y,a,b;
	for(int i = 1; i <= cnt; i ++) {
		fa[i] = i;
	}
	for(int i = 0; i < len1; i ++) {
		int x = a1[i], y = a2[i];
		int a = find(x), b = find(y);
		if(a != b) {
			if(a == 0 && b == 1 || b == 0 && a == 1) {
				cout << 0;
				return 0;
			}
			if(a <= 1) {
				fa[b] = a;
			}
			else {
				fa[a] = b;
			}
		}
	}
	for(int i = 2; i <= cnt; i ++) {
		if(vis[i] && find(i) == i) {
			ans ++;
		}
	}
	cout << (int)pow(2, ans);
	return 0;
}