累積XORだけど生えなかった・・・・(´；ω；`)ｳｯ…

Codeforces Round #571(Div. 2) C Vus the Cossack String

問題概要

２進数の文字列とが与えられる．文字列の連続する部分文字列で，文字列と同じ長さのものと文字列を比較する．この時，文字が異なる位置が偶数個存在する文字列の連続する部分文字列の個数を求める．

問題リンク

https://codeforces.com/contest/1186/problem/C

制約

文字列とは２進数の文字列

考察

• 愚直解から計算量を落とそうといろいろ考えたけどダメだった・・・・
• 累積系の処理をしておくと良さそうな感じはしたけどそこから何も見えてこなかった（おいおい・・・・）
• （Twitterで累積XORの解法を観測・・・）累積XORをとると何が分かるのか？？？・・・・・部分文字列の中にある1の個数の奇偶が分かるな～
• の部分文字列と文字列の各bitを比較して違ったら+1して，最後にこれらが偶数なら解に含まれるというのが愚直な方法になる．bitが違ったら+1になる・・・・bitが同じ場合は無視・・・・・これに該当する演算は・・・・・XORならbitが違う場合は1になる・・・・・これか・・・・・(´；ω；`)ｳｯ…
• 各ビットのXORを取って1になっている部分の個数を数えて偶数になる・・・・これらのXORも0になる感じでは？？・・・・・結局全部XOR取った時に0であればいいのか・・・・？
• 文字列部分文字列との全部のXORが0でなんやねん・・・・（ここでサンプルをグッとにらむ）・・・どうやら文字列部分文字列とに含まれる1の個数の奇偶が同じなら良さそう・・・・・・
• 結局1の個数の奇偶で判定できるのか・・・・ならば文字列部分文字列は累積XORで1の個数の奇偶を求めれば良さそうだし，文字列については固定なので愚直にあらかじめ1の個数を数ればよい（ここでようやく解説と同じところまできた）
• ん～XOR気づきたかったね(´；ω；`)ｳｯ…

ソースコード

※マクロは使っていないので無視してください

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<tuple>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
const ll MOD = 1e9 + 7;
const ll INF = 1e14 + 7;


int main() {

	string s1, s2;

	int s1_siz = s1.size();
	int s2_siz = s2.size();

	vector<int> a(s1.size() + 10, 0);

	for (int i = 1; i <= s1.size(); i++)
	{
		a[i] = s1[i - 1] - '0';
	}

	//累積XOR
	for (int i = 0; i < s1.size(); i++)
	{
		a[i + 1] ^= a[i];
	}

	int cnt = 0;
	for (int i = 0; i < s2.size(); i++)
	{
		if (s2[i] == '1') {
			cnt++;
		}
	}

	cnt %= 2;
	int ans = 0;
	for (int i = s2_siz; i <= s1_siz; i++)
	{
		int tmp = a[i] ^ a[i - s2_siz];
		if (tmp % 2 == cnt) {
			ans++;
		}
	}

	cout << ans << endl;


	return 0;

}