#2380. 多项式

多项式

多项式

题目描述

3 多项式 3.1 题目描述 九条可怜最近研究了一下多项式在系数模2 意义下的性质。她发现可以用多项式在模2 意 义下的乘法得到一个很长的字符串: 对于一个n 次的系数为0 或1 的多项式f(x),我们在模2 意义下计算g(x) = f(x)m,则 g(x) 为一个nm 次的多项式,它有nm + 1 个系数,将这些系数从儈位到վ位写下来,就可以 得到一个长度为nm + 1 的01 字符串。 例如对于多项式f(x) = x3 + x + 1,计算g(x) = f(x)3 = x9 + x7 + x6 + x5 + x2 + x + 1, 这样我们得到了一个长度为10 的字符串1011100111。 现在可怜有一个次数为n 的多项式f(x),整数m, L, R 以及一个长度为K 的01 串t。令s 为f(x)m 得到的字符串,s[L, R] 为s 的第L 个字符到第R 个字符,可怜想要知道t 在s[L, R] 中出现了多少次。 3.2 输入格式 第一行输入一个整数T 表示数据组数。 每组数据第一行输入五个整数n, m, K, L, R。 第二行输入一个长度为n + 1 的01 串表示多项式f(x) 的系数,其中第i 位表示f(x) 的 第n −i + 1 次系数。 第三行输入一个长度为K 的字符串表示字符串t。 3.3 输出格式 对于每组数据输出一个整数表示答案。 3.4 样例输入 1 3 3 2 1 10 1011 01 3.5 样例输出 2 7

3.6 数据范围与约定 测试点编号 n m K 其他约定 1 ≤18 ≤500 ≤18 无 2 ≤2 × 105 3 4 ≤1016 R −L ≤104 5 6 L = 1, R = nm + 1 7 8 9 无 10 对于100% 的数据,保证1 ≤T ≤5,1 ≤L ≤R ≤nm + 1。 8

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
3 3 2 1 10
1011
01
2

样例 2

4
18 425979 3 4394755 5294599
1110011000110000001
101
18 654615 18 8371190 8974716
1110110011000010001
100011111010101011
18 509662 18 525987 5910726
1000010010001100000
010100000101010100
18 446204 18 2628281 3483268
1011011111101001001
000000000100010001
84292
1367
1068
6713