A6660. 「雅礼集训 2018 Day7」B
编程题
提高+/省选-
知识点
题目描述
给定一个长度为 $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$ 个操作或询问：
-
-
$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$ 行，一行表示一个操作或询问，格式如上文所述。
第二行一个长度为 $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$。
- 存在 $40 \%$ 的数据， $n, m, q \leq 5000$。