NKOJ 2106 机密谍报 （并查集）

发表于 |
字数统计: 890字 | 阅读时长 ≈ 4min

P2106 机密谍报

问题描述

HY 非常喜欢和 GJQ 闲聊，而其他人等都还奋斗在 OI 的道路上，为了不打扰同学，他们交流统一用密文，交流信息的明文是由0和1组成的非空序列，而密文是由0、1和若干个密码字母组成，每个 密码字母代表不同的01串，
例如，密文 011a0bf00a01。密码破译的关键是确定每个密码的含义。
经过长期统计分析，现在知道了每个密码的固定长度，如今，蛋疼的同学们又截获了它们俩的两段 密文S1 和S2 ，并且知道S1 =S2 ，即两段密文代表相同的明文。你的任务是帮助同学们对给定的两段密文进行分析，看一看有多少种可能的明文。

输入格式

第 1 行：S1 (第 1 段密文)
第 2 行：S2 (第 2 段密文)
第 3 行：N(密码总数，N ≤ 26)
第 4−N+3 行：字母 i长度i (密码用小写英文字母表示，密码长度 ≤ 100)

输出格式

M（表示有 M种可能的明文）

样例输入

100ad1
cc1
4
a 2
d 3
c 4
b 50

样例输出

2

提示

明文的长度 ≤ 10000，保证不用高精度

此题其实很水，用并查集将相同的位置合并起来，然后再把值为0的位置合并到一个集合里，值为1的位置合并到一个集合里，然后既不在0集合里也不在1集合里的集合数就是不能确定的位置数，答案就是$2^n$

但是注意判无解，如果最后0集合和1集合在一个集合里，即表示某位置既是0又是1，则无解。或者两个串长度不相同，也无解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<assert.h>
#define N 1000005
using namespace std;
const int mod=998244353;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return 1ll*a*b%mod;}
int ksm(int a,int b){int o;for(o=1;b;b>>=1,a=mul(a,a))if(b&1)o=mul(o,a);return o;}
int n,l1,l2,len[26],fa[N],sum1,sum2,S,T,ans;
bool mark[N];
char s1[N],s2[N];
vector<int>pos[26];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void Merge(int x,int y)
{
	x=gf(x);y=gf(y);
	if(x!=y)fa[x]=y;
}
int main()
{
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	int i,j,k,x,y;char c;
	scanf("%s",s1+1);l1=strlen(s1+1);
	scanf("%s",s2+1);l2=strlen(s2+1);
	assert(l1<=1000000);
	assert(l2<=1000000);
	scanf("%d",&n);
	S=1000001;T=S+1;
	for(i=1;i<=T;i++)fa[i]=i;
	for(i=1;i<=n;i++)scanf("\n%c%d",&c,&k),len[c-'a']=k;
	for(i=1;i<=l1;i++)
	{
		if(s1[i]=='0')sum1++,Merge(sum1,S);
		else if(s1[i]=='1')sum1++,Merge(sum1,T);
		else pos[s1[i]-'a'].push_back(sum1),sum1+=len[s1[i]-'a'];
	}
	for(i=1;i<=l2;i++)
	{
		if(s2[i]=='0')sum2++,Merge(sum2,S);
		else if(s2[i]=='1')sum2++,Merge(sum2,T);
		else pos[s2[i]-'a'].push_back(sum2),sum2+=len[s2[i]-'a'];
	}
	for(i=0;i<26;i++)
	for(j=1;j<=len[i];j++)
	for(k=1;k<pos[i].size();k++)Merge(pos[i][k-1]+j,pos[i][k]+j);
	int fx=gf(S),fy=gf(T);
	if(fx==fy||sum1!=sum2)return puts("0"),0;
	for(i=1;i<=sum1;i++)
	{
		x=gf(i);if(x==fx||x==fy)continue;
		if(!mark[x])mark[x]=1,ans++;
	}
	printf("%d\n",ksm(2,ans));
}