#PQJ43x5215. QOJ 43_5215

    ID: 2967 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2017字符串快速幂

QOJ 43_5215

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