#6508. 「雅礼集训 2018 Day7」B

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个长度为 n 的 01 串 S 和一个长度为 m 的 01 串 T

S 通过给定的参数 a, b, c 构造,其中 a 满足 {\rm gcd}(a, n) = 1

S_i = [(a\cdot i + b)\ {\rm mod}\ n \geq c]

现在有 q 个操作或询问:

  • 1 p:询问 S 的第 p 位开始往后取 m 位得到的字符串与 T 有多少位不同
  • 2 p:将 T 的第 p 位取反

输入格式

第一行五个正整数 n, a, b, c, m

第二行一个长度为 m 的字符串表示 T

第三行一个整数 q

接下来 q 行,一行表示一个操作或询问,格式如上文所述。

输出格式

对于每一个询问,输出一行一个整数表示答案。

样例

样例输入 1

9 5 6 4 3
101
11
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 1
1 3

样例输出 1

0
3
0
2
2
0
3
0
3
1

数据范围与提示

对于全部数据, 1 \leq a, b, p, m < n \leq 10^9, 1 \leq m, q \leq 100000, {\rm gcd}(a, n) = 1

  • 存在 40 \% 的数据, n, m, q \leq 5000