問題一覧 > 教育的問題

No.2273 Point Multiply/Divide, Range Product

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : 👑 p-adic / テスター : ecottea
お気に入りにしたユーザー ProblemId : 9078 / 自分の提出
問題文最終更新日: 2023-04-11 23:31:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 384 (順位表) の他の問題:

Note

The time limit for this problem is 5000[ms].

 

Problem Statement

You are given as input $3$ positive integers $N, B, Q$, a sequence $A$ of non-negative integers of length $N$, and $Q$ queries (described later).

 

First, we introduce some notation. For a sequence $a$ of non-negative integers and a non-negative integer $i$ less than its length, $a_i$ denotes the $1+i$-th element of $a$.

Furthermore, for $2$ non-negative integers $\ell, r$ less than the length of $a$ satisfying $\ell \leq r$, let

$\displaystyle \left( \prod_{i = \ell}^{r} a_i \right) \bmod B $

be denoted by $P_B(a,\ell,r)$.

Also, for non-negative integers $k,m$, define the non-negative integer $R_B(k,m)$ as follows:

  • If $k$ is a multiple of $B$ and $m = B$, then $R_B(k,m) = B^{-1} k$.
  • Otherwise, $R_B(k,m) = m k$.

 

Now we move on to the main problem. Each query is a tuple $(j,m,\ell,r)$ of $4$ non-negative integers $j,m,\ell, r$ satisfying $j < N$ and $\ell \leq r < N$.

A query $(j,m,\ell,r)$ is processed as follows:

  1. First, update $A$ by replacing the value of the $1+j$-th element of $A$ from $A_j$ to $R_B(A_j,m)$.
  2. Next, find $P_B(A,\ell,r)$ for the updated $A$. (Hereafter, this value is called the answer to that query.)

Process all $Q$ queries in the given order.

Input

The input is given from standard input in the following format:

  • The $1$st line contains $N, B, Q$, separated by single-byte spaces.
  • The $2$nd line contains the elements of $A$, separated by single-byte spaces.
  • For each positive integer $q$ not exceeding $Q$, line $2 + q$ contains the components of the $q$-th query $(j,m,\ell,r)$, separated by single-byte spaces.

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$
  • $Q$ is an integer satisfying $1 \leq Q \leq 10^5$
  • For every non-negative integer $i$ less than $N$, $A_i$ is an integer satisfying $0 \leq A_i \leq 10^{18}$
  • Every query $(j,m,\ell,r)$ satisfies the following:
    • $j$ is an integer satisfying $0 \leq j < N$
    • $m$ is an integer satisfying $0 \leq m \leq 10^{18}$
    • $\ell$ and $r$ are integers satisfying $0 \leq \ell \leq r < N$

Output

For each positive integer $q$ not exceeding $Q$, output the answer to the $q$-th query on line $q$.

Print a newline at the end.

Sample

Sample 1
Input
1 2 1
1
0 3 0 0
Output
1

We process the query $(j,m,\ell,r) = (0,3,0,0)$. $A = (1)$ is updated to

$\displaystyle (R_B(A_0,m)) = (R_2(1,3)) = (3 \times 1) = (3) $

and for the updated $A$ we have

$\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 $

so the answer to this query is $1$. Since $Q = 1$ here, all processing is now finished.

Sample 2
Input
2 3 1
1 2
0 2 0 1
Output
1

We process the query $(j,m,\ell,r) = (0,2,0,1)$. $A = (1,2)$ is updated to

$\displaystyle (R_B(A_0,m),A_1) = (R_3(1,2),2) = (2 \times 1,2) = (2,2) $

and for the updated $A$ we have

$\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 $

so the answer to this query is $1$. Since $Q = 1$ here, all processing is now finished.

Sample 3
Input
2 3 2
6 2
1 2 0 1
0 3 0 0
Output
0
2

First, we process the $1$st query $(j,m,\ell,r) = (1,2,0,1)$. $A = (6,2)$ is updated to

$\displaystyle (A_0,R_B(A_1,m)) = (6,R_3(2,2)) = (6,2 \times 2) = (6,4) $

and for the updated $A$ we have

$\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 $

so the answer to this query is $0$.

Next, we process the $2$nd query $(j,m,\ell,r) = (0,3,0,0)$. $A = (6,4)$ is updated to

$\displaystyle (R_B(A_0,m),A_1) = (R_3(6,3),4) = (3^{-1} \times 6,4) = (2,4) $

and for the updated $A$ we have

$\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 $

so the answer to this query is $2$. Since $Q = 2$ here, all processing is now finished.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。