SRM516 Div1Easy NetworkXOneTimePad

考察

全てのciphertextが、plaintextsの内どれか1つに戻るようなkeyの数を求める。xorの性質を考えるとこれは、

写像 key: ciphertexts → plaintexts が単射であるような、keyの数を求める

と言い換えられる(ﾎﾝﾄ?)

そんなことは割とどうでもよくて、結局やることはciphertexts[0]をplaintexts[i]に戻せるようなkeyが他のciphertextも戻せるかの確認。

実装

$50^{4}$ が間に合うのか確認するのがだるかった(≒ $O(N^{4})$ を嫌った)ので、stringをlong longに変換。これで前計算 $2\times 50^{2}$ 、実行 $50^{3}$ で確実に間に合う。ここまでやっといて^(xor)の計算量が $O(1)$ じゃなかったら笑う。

#include <bits/stdc++.h>
using namespace std;

class NetworkXOneTimePad {
public:
    int crack( vector <string> plaintexts, vector <string> ciphertexts ){
        vector<long long> p,c;
        for(auto i:plaintexts){
            string s=i; reverse(s.begin(),s.end());
            long long a=1,sum=0;
            for(auto j:i){
                sum+=a*(j-'0');
                a<<=1;
            }
            p.push_back(sum);
        }
        for(auto i:ciphertexts){
            string s=i; reverse(s.begin(),s.end());
            long long a=1,sum=0;
            for(auto j:i){
                sum+=a*(j-'0');
                a<<=1;
            }
            c.push_back(sum);
        }
        int ret=0;
        for(auto i:p){
            long long key=c[0]^i;
            bool flg1=1;
            for(auto j:c){
                bool flg2=0;
                for(auto k:p){
                    if((j^key)==k) flg2=1;
                }
                if(!flg2) flg1=0;
            }
            if(flg1) ret++;
        }
        return ret;
    }
};