正文

Vus the Cossack and Strings（Codeforces Round #571 (Div. 2)）（大佬的位运算实在是太强了！）

IP云
IP云V管理员/0 阅读
10/03
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

C. Vus the Cossack and Strings

Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings aa and bb. It is known that |b|≤|a||b|≤|a|, that is, the length of bb is at most the length of aa.

The Cossack considers every substring of length |b||b| in string aa. Let's call this substring cc. He matches the corresponding characters in bband cc, after which he counts the number of positions where the two strings are different. We call this function f(b,c)f(b,c).

For example, let b=00110b=00110, and c=11000c=11000. In these strings, the first, second, third and fourth positions are different.

Vus the Cossack counts the number of such substrings cc such that f(b,c)f(b,c) is even.

For example, let a=01100010a=01100010 and b=00110b=00110. aa has four substrings of the length |b||b|: 0110001100, 1100011000, 1000110001, 0001000010.

  • f(00110,01100)=2f(00110,01100)=2;
  • f(00110,11000)=4f(00110,11000)=4;
  • f(00110,10001)=4f(00110,10001)=4;
  • f(00110,00010)=1f(00110,00010)=1.

Since in three substrings, f(b,c)f(b,c) is even, the answer is 33.

Vus can not find the answer for big strings. That is why he is asking you to help him.

Input

The first line contains a binary string aa (1≤|a|≤1061≤|a|≤106) — the first string.

The second line contains a binary string bb (1≤|b|≤|a|1≤|b|≤|a|) — the second string.

Output

Print one number — the answer.

Examples
input
Copy

01100010
00110

output
Copy

3

input
Copy

1010111110
0110

output
Copy

4

Note

The first example is explained in the legend.

In the second example, there are five substrings that satisfy us: 10101010, 01010101, 11111111, 11111111.

题意：题目给了一个较长字符串a以及一个较短字符串b，在a中取与b长度相等的子串，比较子串与b字符串中有几组字符不一样。

当天下午由于在探讨研究这场CF B题的4 4 情况，而导致后来没怎么看这道题，但实际上这道题对于位运算的运用是十分的基础而且有效的。

顺带一提，B题4 4的情况，不仅hack掉了基本所有的AC代码，甚至让这场比赛都不算rate了

先科普一下 位运算中的 异或（运算符"^"）,在二进制中，如果两个数字相同的话，那么异或的结果就是0，否则就是1；同时两次异或同一个数字，就相当于没有没有异或过这个数字

先贴一下代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = ;
char a[maxn],b[maxn];
int ans = ,sum = ;
int main(){
scanf("%s",a);
scanf("%s",b);
int len_a = strlen(a);
int len_b = strlen(b);
for(int i = ; i < len_b ; i++){
ans=ans^a[i]^b[i];
}
if(ans% == ) sum++;
for(int i = len_b ; i < len_a ; i++){
ans = ans^a[i-len_b]^a[i];
if(ans % == ) sum++;
}
printf("%d\n",sum);
return ;
}

C

例如，样例一:

一开始先对于 i = 0  到 i = strlen（b） 中 b 字符串和a的子串进行异或操作，如果异或结果(ans)可以整除2，那么就代表这个子串对于b而言有偶数组不同。

之后就可以有i = len 向 i = strlen（a）中逐位挪移，而计算结果就是  新的 ans  =  旧的 ans ^ a[i - len] ^ a[i])。^a[i - len]就是消除a[i - len]的影响，^a[i]就是将a[i]的影响加入计算

一开始的状态

（0^0）^（1^0）^（1^1）^（0^1）^（0^0）

向右挪移一位

（0^0）^（1^0）^（1^1）^（0^1）^（0^0）^0^0   // 第一个0 是a[i - len],第二个0是a[i];

= 0^（0^0）^（1^0）^（1^1）^（0^1）^（0^0）^0  // 因为一个数字异或两次相当于没有异或

= ·（0^1）^（0^1）^（1^0）^（1^0）^（0^0）

这样只需要O（n）的时间复杂度就可以完成运算。

一个从很久以前就开始做的梦。