P2106 機(jī)密諜報(bào)

　　問(wèn)題描述

　　HY 非常喜歡和 GJQ 閑聊，而其他人等都還奮斗在 OI 的道路上，為了不打擾同學(xué)，他們交流統(tǒng)一用密文，交流信息的明文是由0和1組成的非空序列，而密文是由0、1和若干個(gè)密碼字母組成，每個(gè) 密碼字母代表不同的01串，

　　例如，密文 011a0bf00a01。密碼破譯的關(guān)鍵是確定每個(gè)密碼的含義。

　　經(jīng)過(guò)長(zhǎng)期統(tǒng)計(jì)分析，現(xiàn)在知道了每個(gè)密碼的固定長(zhǎng)度，如今，蛋疼的同學(xué)們又截獲了它們倆的兩段 密文S1 和S2 ，并且知道S1 =S2 ，即兩段密文代表相同的明文。你的任務(wù)是幫助同學(xué)們對(duì)給定的兩段密文進(jìn)行分析，看一看有多少種可能的明文。

　　輸入格式

　　輸出格式

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

　　樣例輸入

　　100ad1

　　cc1

　　4

　　a 2

　　d 3

　　c 4

　　b 50

　　樣例輸出

　　2

　　提示

　　明文的長(zhǎng)度 ≤ 10000，保證不用高精度

　　此題其實(shí)很水，用并查集將相同的位置合并起來(lái)，然后再把值為0的位置合并到一個(gè)集合里，值為1的位置合并到一個(gè)集合里，然后既不在0集合里也不在1集合里的集合數(shù)就是不能確定的位置數(shù)，答案就是2 n 但是注意判無(wú)解，如果最后0集合和1集合在一個(gè)集合里，即表示某位置既是0又是1，則無(wú)解。

　　代碼：

　　#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(xiàn)［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（“\n%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”）;

　　}