#P1736. 2024.3.24-PDD-第二题-异或生成的串个数
2024.3.24-PDD-第二题-异或生成的串个数
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥拥有两个仅由0和1组成的字符串A,B,其中A的长度为m,B的长度为n,字符串下标都从0开始。现在塔子哥定义了一种字符串生成模式:
(1)从字符串A中选择一个下标i,其中0≤i≤m−n;
(2)从下标i开始,获取字符串A一个长度为n的连续子串;
(3)将取出的子串各字符依次与字符串B中各字符作异或运算,最终生成一个字符串。
例如,字符串A为10101,字符串B为01,则当i=0时,生成的字符串为11。当i=1时,生成的字符串为00。
现在定义生成的字符串合法条件为,当且仅当生成的字符串各个字符异或的结果为0,更正规的,假设合法的生成的字符串为S,S的长度恒等于n,对于所有0≤i<n,有S[0]^S[1]^...^S[n-1]=0。比如上面的例子中,生成的两个字符串都是合法的。
现在塔子哥想问你,对于给定的字符串A和B,一共有多少种不同的子串可以生成合法的串?
定义两个字符串不同,当对两个串相同下标对应的字符不同,即为字符串不同,例如字符串10和01不相同。
第一行输入两个整数m和n,分别表示字符串A和B的长度。其中1≤n≤m≤5000
第二行输入字符串A,第三行输入字符串B。
输出一个整数,表示不同的子串个数。
输入
8 2
10100000
01
输出
2
输出解释
用子串10和01生成串合法串11和00,两个用于生成的子串10和01互不相同,所以结果为2。
1s, 1024KiB for each test case.
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.