[ZJOI2017] 多项式
题目描述
九条可怜最近研究了一下多项式在系数模 2 意义下的性质。她发现可以用多项式在模 2 意义下的乘法得到一个很长的字符串:
对于一个 $n$ 次的系数为 0 或 1 的多项式 $f\left ( x \right )$,我们在模 2 意义下计算 $g\left ( x \right ) = f\left ( x \right )^{m}$,则
$g\left ( x \right )$ 为一个 $nm$ 次的多项式,它有 $nm + 1$ 个系数,将这些系数从**高位到低位**写下来,就可以得到一个长度为 $nm + 1$ 的 01 字符串。
例如对于多项式 $f\left ( x \right ) = x^{3} + x + 1$,计算 $g\left( x \right ) = f\left( x \right)^{3} = x^{9} + x^{7} + x^{6} + x^{5} + x^{2} + x^{1} + 1 $,这样我们得到了一个长度为 10 的字符串 1011100111。
现在可怜有一个次数为 $n$ 的多项式 $f\left( x \right )$,整数 $m$, $L$, $R$ 以及一个长度为 $K$ 的 01 串 $t$。令 $s$为 $f\left( x \right )^{m}$得到的字符串, $s\left[L, R\right]$ 为 $s$ 的第 $L$ 个字符到第 $R$ 个字符,可怜想要知道 $t$ 在 $s\left[L, R\right]$中出现了多少次。
输入输出格式
输入格式
第一行输入一个整数 T 表示数据组数。
每组数据第一行输入五个整数 $n, m, K, L, R$。
第二行输入一个长度为 $n + 1$ 的 01 串表示多项式 $f\left( x \right )$ 的系数,其中第 $i$ 位表示 $f\left( x \right )$ 的第 $n − i + 1$ 次系数。
第三行输入一个长度为 $K$ 的字符串表示字符串 $t$。
输出格式
对于每组数据输出一个整数表示答案。
输入输出样例
输入样例 #1
1
3 3 2 1 10
1011
01
输出样例 #1
2
说明
**时空限制**
时间限制3s,空间限制512M
**数据范围**
![](https://cdn.luogu.com.cn/upload/pic/4746.png)