No.2273 一点乗除区間積
タグ : / 解いたユーザー数 12
作問者 : 👑
p-adic
/ テスター :
ecottea
注意
この問題の実行時間制限は5000[ms]です。
問題文
入力に $3$ 個の正整数 $N, B, Q$ と、長さ $N$ の非負整数列 $A$ と $Q$ 個のクエリ（後述） が与えられます。
まずは記法の導入です。非負整数列 $a$ とその長さ未満の非負整数 $i$ に対し、$a_i$ で $a$ の $1+i$ 個目の成分を表します。
更に $\ell \leq r$ を満たす $a$ の長さ未満の $2$ 個の非負整数 $\ell, r$に対し、
$\displaystyle \left( \prod_{i = \ell}^{r} a_i \right) \bmod B $
を $P_B(a,\ell,r)$ と置きます。
また非負整数 $k,m$ に対し、非負整数 $R_B(k,m)$ を以下のように定めます：
- $k$ が $B$ の倍数でありかつ $m = B$ ならば、$R_B(k,m) = B^{-1} k$ である。
- そうでないならば、$R_B(k,m) = m k$ である。
それでは本題に移ります。各クエリは、$j < N$ と $\ell \leq r < N$ を満たす $4$ 個の非負整数 $j,m,\ell, r$ の組 $(j,m,\ell,r)$ です。
クエリ $(j,m,\ell,r)$ は以下のように処理します：
- まず $A$ の $1+j$ 個目の成分の値を $A_j$ から $R_B(A_j,m)$ に置き換えることで $A$ を更新する。
- 次に更新された $A$ に対する $P_B(A,\ell,r)$ を求める。（以下この値を、そのクエリへの回答と呼ぶ）
$Q$ 個のクエリを与えられた順に全て処理してください。
入力
入力は以下の形式で標準入力から与えられます：
- $1$ 行目に $N, B, Q$ が半角空白区切り与えられます。
- $2$ 行目に $A$ の各成分が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$2 + q$ 行目に $q$ 個目のクエリ $(j,m,\ell,r)$ の各成分が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数
- $B$ は $1 \leq B \leq 10^9$ を満たす整数
- $Q$ は $1 \leq Q \leq 10^5$ を満たす整数
- $N$ 未満の任意の非負整数 $i$ に対し、$A_i$ は $0 \leq A_i \leq 10^{18}$ を満たす整数
- 全てのクエリ $(j,m,\ell,r)$ が以下を満たす：
- $j$ は $0 \leq j < N$ を満たす整数
- $m$ は $0 \leq m \leq 10^{18}$ を満たす整数
- $\ell$ と $r$ は $0 \leq \ell \leq r < N$ を満たす整数
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリへの回答を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 1 1 0 3 0 0
出力
1
クエリ $(j,m,\ell,r) = (0,3,0,0)$ を処理します。$A = (1)$ が
$\displaystyle (R_B(A_0,m)) = (R_2(1,3)) = (3 \times 1) = (3) $
に更新され、更新後の $A$ に対し
$\displaystyle P_B(A,\ell,r) = P_2(A,0,0) = \left( \prod_{i = 0}^{0} A_i \right) \bmod 2 = 3 \bmod 2 = 1 $
となるので、このクエリへの回答は $1$ です。今回は $Q = 1$ であるので、これで全ての処理が終了します。
サンプル2
入力
2 3 1 1 2 0 2 0 1
出力
1
クエリ $(j,m,\ell,r) = (0,2,0,1)$ を処理します。$A = (1,2)$ が
$\displaystyle (R_B(A_0,m),A_1) = (R_3(1,2),2) = (2 \times 1,2) = (2,2) $
に更新され、更新後の $A$ に対し
$\displaystyle P_B(A,\ell,r) = P_3(A,0,1) = \left( \prod_{i = 0}^{1} A_i \right) \bmod 3 = (2 \times 2) \bmod 3 = 4 \bmod 3 = 1 $
となるので、このクエリへの回答は $1$ です。今回は $Q = 1$ であるので、これで全ての処理が終了します。
サンプル3
入力
2 3 2 6 2 1 2 0 1 0 3 0 0
出力
0 2
まず $1$ 個目のクエリ $(j,m,\ell,r) = (1,2,0,1)$ を処理します。$A = (6,2)$ が
$\displaystyle (A_0,R_B(A_1,m)) = (6,R_3(2,2)) = (6,2 \times 2) = (6,4) $
に更新され、更新後の $A$ に対し
$\displaystyle P_B(A,\ell,r) = P_3(A,0,1) = \left( \prod_{i = 0}^{1} A_i \right) \bmod 3 = (6 \times 4) \bmod 3 = 24 \bmod 3 = 0 $
となるので、このクエリへの回答は $0$ です。
引き続き $2$ 個目のクエリ $(j,m,\ell,r) = (0,3,0,0)$ を処理します。$A = (6,4)$ が
$\displaystyle (R_B(A_0,m),A_1) = (R_3(6,3),4) = (3^{-1} \times 6,4) = (2,4) $
に更新され、更新後の $A$ に対し
$\displaystyle P_B(A,\ell,r) = P_3(A,0,0) = \left( \prod_{i = 0}^{0} A_i \right) \bmod 3 = 2 \bmod 3 = 2 $
となるので、このクエリへの回答は $2$ です。今回は $Q = 2$ であるので、これで全ての処理が終了します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。