4277: 「ZJOI2017」多项式
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
九条可怜最近研究了一下多项式在系数模 $2$ 意义下的性质。她发现可以用多项式在模 $2$ 意义下的乘法得到一个很长的字符串：
对于一个 $n$ 次的系数为 $0$ 或 $1$ 的多项式 $f(x)$，我们在模 $2$ 意义下计算 $g(x) = f(x)^m$，则 $g(x)$ 为一个 $nm$ 次的多项式，它有 $nm + 1$ 个系数，将这些系数从**高位到低位**写下来，就可以得到一个长度为 $nm + 1$ 的 $01$ 字符串。
例如对于多项式 $f(x) = x^3 + x + 1$，计算 $g(x) = f(x)^3 = x^9 + x^7 + x^6 + x^5 + x^2 + 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$ 。
输出
对于每组数据输出一个整数表示答案。
样例输入 复制
1
3 3 2 1 10
1011
01样例输出 复制
2提示
数据范围：| 测试点编号 | $n$ | $m$ | $K$ | 其他约定 | | :--------: | :------: | :----------------: | :------: | :-----------: | | $1$ | $\le 18$ | $\le 500$ | $\le 18$ | 无 | | $2$ | $\le 18$ | $\le 2\times 10^5$ | $\le 18$ | 无 | | $3$ | $\le 18$ | $\le 2\times 10^5$ | $\le 18$ | 无 | | $4$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | $R-L\le 10^4$ | | $5$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | $R-L\le 10^4$ | | $6$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | $L=1,R=nm+1$ | | $7$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | $L=1,R=nm+1$ | | $8$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | $L=1,R=nm+1$ | | $9$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | 无 | | $10$ | $\le 18$ | $\le 10^{16}$ | $\le 18$ | 无 | 对于$100\%$ 的数据，保证 $1\leq T\leq 5$，$1\leq L\leq R \leq nm + 1$。