AT_abc156_f [ABC156F] Modularness

题目描述

有一个长度为 $k$ 的数列 $d_0, d_1, \ldots, d_{k-1}$。

请依次处理以下 $q$ 个查询。

• 第 $i$ 个查询包含三个整数 $n_i, x_i, m_i$。定义长度为 $n_i$ 的数列 $a_0, a_1, \ldots, a_{n_i-1}$，其递推关系如下：

$$\begin{aligned} a_j = \begin{cases} x_i & (j = 0) \\ a_{j-1} + d_{(j-1)\bmod k} & (0 < j \leq n_i - 1) \end{cases} \end{aligned}$$

请输出满足 $(a_j \bmod m_i) < (a_{j+1} \bmod m_i)$ 的 $j$ 的个数，其中 $0 \leq j < n_i - 1$。

这里，对于两个整数 $y, z\ (z > 0)$，$(y \bmod z)$ 表示 $y$ 除以 $z$ 的余数。

输入格式

输入按以下格式从标准输入读入。

$k$ $q$ $d_0$ $d_1$ $\ldots$ $d_{k-1}$ $n_1$ $x_1$ $m_1$ $n_2$ $x_2$ $m_2$ $\ldots$ $n_q$ $x_q$ $m_q$

输出格式

输出 $q$ 行。

第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

3 1
3 1 4
5 3 2

输出 #1

1

输入输出样例 #2

输入 #2

7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12

输出 #2

224489796
214285714
559523809

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq k, q \leq 5000$
• $0 \leq d_i \leq 10^9$
• $2 \leq n_i \leq 10^9$
• $0 \leq x_i \leq 10^9$
• $2 \leq m_i \leq 10^9$

样例解释 1

对于第 $1$ 个查询，按照题意构造的数列 $\{a_j\}$ 为 $3, 6, 7, 11, 14$。

• $(a_0 \bmod 2) > (a_1 \bmod 2)$
• $(a_1 \bmod 2) < (a_2 \bmod 2)$
• $(a_2 \bmod 2) = (a_3 \bmod 2)$
• $(a_3 \bmod 2) > (a_4 \bmod 2)$

因此，该查询的答案为 $1$。

由 ChatGPT 4.1 翻译