P2106 机密谍报（电脑菜鸟体验做高手心理）

　　P2106 机密谍报

　　问题描述

　　HY 非常喜欢和 GJQ 闲聊，而其他人等都还奋斗在 OI 的道路上，为了不打扰同学，他们交流统一用密文，交流信息的明文是由0和1组成的非空序列，而密文是由0、1和若干个密码字母组成，每个 密码字母代表不同的01串，

　　例如，密文 011a0bf00a01。密码破译的关键是确定每个密码的含义。

　　经过长期统计分析，现在知道了每个密码的固定长度，如今，蛋疼的同学们又截获了它们俩的两段 密文S1 和S2 ，并且知道S1 =S2 ，即两段密文代表相同的明文。你的任务是帮助同学们对给定的两段密文进行分析，看一看有多少种可能的明文。

　　输入格式

　　输出格式

　　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，则无解。

　　代码：

　　#include《stdio.h》

　　#include《iostream》

　　#include《algorithm》

　　#include《cstring》

　　#include《vector》

　　#define N 55555

　　#define ll unsigned long long

　　using namespace std;

　　const ll T=40000;

　　string s1，s2;

　　vector《ll》P［233］;

　　char A［233］;

　　ll n，L［233］，sum1［N］，sum2［N］，F［N］;

　　bool mark［N］;

　　ll GF（ll x）

　　{

　　if（F［x］！=x）F［x］=GF（F［x］）;

　　return F［x］;

　　}

　　void Merge（ll x，ll y）

　　{

　　ll fx=GF（x），fy=GF（y）;

　　if（fx！=fy）F［fx］=fy;

　　}

　　ll QM（ll a，ll b）

　　{

　　ll ans=1;

　　while（b）

　　{

　　if（b&1）ans=ans*a;

　　b》》=1;a=a*a;

　　}

　　return ans;

　　}

　　int main（）

　　{

　　ll i，j，k，ans;ans=0;

　　cin》》s1》》s2;

　　s1=“ ”+s1;s2=“ ”+s2;

　　scanf（“%lld”，&n）;

　　for（i=1;i《=n;i++）scanf（“ %c %lld”，&A［i］，&k），L［A［i］］=k;

　　for（i=1;i《=T;i++）F［i］=i;

　　for（i=1;i《s1.length（）;i++）

　　if（s1［i］==‘0’）sum1［i］=sum1［i-1］+1，Merge（sum1［i］，T）;

　　else if（s1［i］==‘1’）sum1［i］=sum1［i-1］+1，Merge（sum1［i］，T+1）;

　　else sum1［i］=sum1［i-1］+L［s1［i］］，P［s1［i］］.push_back（sum1［i-1］）;

　　for（i=1;i《s2.length（）;i++）

　　if（s2［i］==‘0’）sum2［i］=sum2［i-1］+1，Merge（sum2［i］，T）;

　　else if（s2［i］==‘1’）sum2［i］=sum2［i-1］+1，Merge（sum2［i］，T+1）;

　　else sum2［i］=sum2［i-1］+L［s2［i］］，P［s2［i］］.push_back（sum2［i-1］）;

　　for（i=1;i《=n;i++）

　　for（j=1;j《=L［A［i］］;j++）

　　for（k=1;k《P［A［i］］.size（）;k++）Merge（P［A［i］］［k-1］+j，P［A［i］］［k］+j）;

　　for（i=1;i《=sum1［s1.length（）-1］;i++）if（GF（i）！=GF（T）&&GF（i）！=GF（T+1）&&（！mark［GF（i）］））ans++，mark［GF（i）］=1;

　　if（GF（T）！=GF（T+1））printf（“%lld”，QM（2，ans））;

　　else printf（“0”）;

　　}