Confidential Intelligence P2106
Problem Description
HY is very fond of chatting with GJQ, while others are still struggling in the world of OI. To avoid disturbing the students, they exchange encrypted messages. The plaintext of their communication is a non-empty sequence made up of 0s and 1s. It also contains several password letters, each representing a different binary string.
For example, the ciphertext "011a0bf00a01" could be interpreted as a combination of binary sequences and letters. The key to decrypting this message is to determine what each password letter stands for.
After long-term statistical analysis, it is now known that each password has a fixed length. The students have intercepted two ciphertexts, S1 and S2, and know that they represent the same plaintext. Your task is to determine how many possible plaintexts can exist based on these two ciphertexts.
Input Format
Output Format
M (indicating the number of possible plaintexts)
Sample Input
100ad1
Cc1
4
a 2
d 3
c 4
b 50
Sample Output
2
Hint
The length of the plaintext is ≤ 10000, and no high precision is required.
This question is actually quite straightforward. You need to compare the two ciphertexts and merge the positions that are the same. Then, group all positions that have the value 0 into one set, and those with value 1 into another. Positions that are not in either set are considered unknown. The number of such sets determines the number of possibilities. The answer is 2 raised to the power of the number of unknown positions. However, if there's a conflict where a position is both 0 and 1, then there is no valid solution.
Code:
#include
#include
#include
#include
#include
#define N 55555
#define ll unsigned long long
using namespace std;
const ll T=40000;
string s1,s2;
vectorP[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;iP03 Series Push Wire Connectors
Smaller size, space saving
Fast connection
111
Push-in Cable Connector,Dual Poles Quick Wire Connectors,fast connection cable connectors,cable managing connectors
Jiangmen Krealux Electrical Appliances Co.,Ltd. , https://www.krealux-online.com
