[ZJOI2017]多项式

九条可怜最近研究了一下多项式在系数模 2 意义下的性质。她发现可以用多项式在模 2 意义下的乘法得到一个很长的字符串：

对于一个 n 次的系数为 0 或 1 的多项式 f(x)，我们在模 2 意义下计算 g(x)=f(x)^m，则 g(x) 为一个 nm 次的多项式，它有 nm+1 个系数，将这些系数从高位到低位写下来，就可以得到一个长度为 nm+1 的 01 字符串。

例如对于多项式 f(x)=x³+x+1，计算g(x)=f(x)³=x⁹+x⁷+x⁶+x⁵+x²+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] 中出现了多少次。

第一行输入一个整数 T 表示数据组数。
每组数据第一行输入五个整数 n,m,K,L,R。
第二行输入一个长度为 n+1 的 01 串表示多项式 f(x) 的系数，其中第 i 位表示 f(x) 的第 n−i+1 次系数。
第三行输入一个长度为 K 的字符串表示字符串 t。

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

详情