SRM516 Div1 Easy - NetworkXOneTimePad

問題

cypher textリストに載っている任意の数字cについて「plain textリストのどれかの数字pを暗号化キーXでxorするとcになる」が成り立つようなキーの数を求める

解法

条件は「各cとXのxorは必ずplain textリストに載っている」と言い換えられる
各cypher textと各plain textをxorしてできる文字列全てが答えの候補で、それらについてこの条件を満たしているかチェックすればいい

考えてみるとcypher textどれか1つと各plain textとのxorを全部調べるだけで十分なことがわかる
(その適当なcypher textをc、それとは違うcypher textをdとして、c^p[i]で生成されないキーXをd^p[i]で生成できるとき、c^Xは明らかにplain textリストに存在しないからチェックする必要がない)
けどこれ考えなくても最悪計算量50^5 = 3*10^8なら通るか🤔

class NetworkXOneTimePad {
	public:
	string xo(string &a, string &b) {
		string res;
		rep(i,a.size()) res += (a[i]==b[i] ? "0" : "1");
		return res;
	}
	
	int crack(vector<string> p, vector<string> c) {
		int n = c.size(), s = p.size(), res = 0;
		rep(k,s) {
			string x = xo(p[k], c[0]);
			bool ok = 1;
			rep(i,n) if (!count(all(p), xo(c[i], x))) ok = 0;
			res += ok;
		}
		return res;
	}
};