問題一覧 > ネタ問題

No.8112 Polynomial with Range Sum Coefficients?

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : 👑 p-adic / テスター : Shirotsume
お気に入りにしたユーザー ProblemId : 10632 / 自分の提出
問題文最終更新日: 2024-04-01 20:16:29
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 April Fool Contest 2024 (順位表) の他の問題:

Note

This is a joke problem created for April Fool Contest 2024.

The problem itself contains no lies, but it may be difficult to solve it through a straightforward approach.

The time limit for this problem is 6000[ms]. Using a fast language and implementation is recommended.

For reference, the writer's solution takes 2207[ms] in c++ and 2691[ms] in PyPy3, and gets TLE in Python3.

Problem Statement

You are given $3$ positive integers $N, B, Q$ and $10$ non-negative integers $C_1, D_1, C_2, D_2, C_3, D_3, C_4, D_4, C_5, D_5$ as input.

Initially, a sequence of non-negative integers $A$ of length $N$ is given as a geometric progression with first term $C_1$ and common ratio $D_1$.

 

First, we introduce some notation. For each non-negative integer $i$ less than $N$, $A_i$ denotes the $1+i$-th element of $A$.

For each positive integer $i$, let $\nu_2(i)$ be the $2$-adic additive valuation of $i$ (the number of times it is divisible by $2$), and define $p(i) = i - 2^{\nu_2(i)}$.

For each non-negative integer $j$ less than $N$ and each non-negative integer $y$, define the non-negative integer $f(j,y)$ recursively using $A$ as follows:

$\displaystyle f(j,y) = \left\{ \begin{array}{ll} A_0 & (j = 0) \\ y f(p(j),y) + \sum_{i=p(j)+1}^{j} A_i & (j \neq 0) \end{array} \right. $

Here is an explanation for those unfamiliar with recursive definitions. (Click to open)

 

Since $p(i) < i$ holds for any positive integer $i$, repeatedly applying $p$ to $j$ eventually reaches $0$. Letting $d$ be the number of applications, we can write

$ f(j,y) = y^d A_0 + \sum_{n=0}^{d-1} \left( \sum_{p^{n+1}(j)+1}^{p^n(j)} A_i \right) y^n $

The right-hand side is a polynomial in $y$ whose coefficients are range sums of $A$.

 

Process the $Q$ queries described below.

 

Each query is a tuple $(i,j,x,y)$ of $2$ non-negative integers $i,j$ less than $N$ and $2$ non-negative integers $x,y$.

A query $(i,j,x,y)$ is processed as follows:

  1. First, update $A$ by replacing $A_i$, the $1 + i$-th element of $A$, with $x$.
  2. Next, find the remainder when $f(j,y)$ for the updated $A$ is divided by $B$. (Hereafter, this value is called the answer to this query.)

However, the queries are not given in the input. For each positive integer $q$ not exceeding $Q$, the $q$-th query $(i,j,x,y)$ is defined as

$\displaystyle (i,j,x,y) = ((C_2 D_2^{q-1}) \bmod N, (C_3 D_3^{q-1}) \bmod N, C_4 D_4^{q-1}, C_5 D_5^{q-1}) $

Here, for a non-negative integer $n$, $n \bmod N$ denotes the remainder when $n$ is divided by $N$, and $0^0$ is defined as $1$.

Input

The input is given from Standard Input in $6$ lines in the following format:

  • The $1$-st line contains $N, B, Q$ separated by half-width spaces.
  • The $2$-nd line contains $C_1, D_1$ separated by half-width spaces.
  • The $3$-rd line contains $C_2, D_2$ separated by half-width spaces.
  • The $4$-th line contains $C_3, D_3$ separated by half-width spaces.
  • The $5$-th line contains $C_4, D_4$ separated by half-width spaces.
  • The $6$-th line contains $C_5, D_5$ separated by half-width spaces.
$N$ $B$ $Q$
$C_1$ $D_1$
$C_2$ $D_2$
$C_3$ $D_3$
$C_4$ $D_4$
$C_5$ $D_5$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq \textcolor{brown}{10^7}$.
  • $B$ is an integer satisfying $1 \leq B \leq \textcolor{red}{10^9}$.
  • $Q$ is an integer satisfying $1 \leq Q \leq \textcolor{blue}{10^6}$.
  • $C_1$ is an integer satisfying $0 \leq C_1 \leq \textcolor{red}{10^9}$.
  • $D_1$ is an integer satisfying $0 \leq D_1 \leq \textcolor{red}{10^9}$.
  • $C_2$ is an integer satisfying $0 \leq C_2 \leq \textcolor{brown}{10^7}$.
  • $D_2$ is an integer satisfying $0 \leq D_2 \leq \textcolor{brown}{10^7}$.
  • $C_3$ is an integer satisfying $0 \leq C_3 \leq \textcolor{brown}{10^7}$.
  • $D_3$ is an integer satisfying $0 \leq D_3 \leq \textcolor{brown}{10^7}$.
  • $C_4$ is an integer satisfying $0 \leq C_4 \leq \textcolor{red}{10^9}$.
  • $D_4$ is an integer satisfying $0 \leq D_4 \leq \textcolor{red}{10^9}$.
  • $C_5$ is an integer satisfying $0 \leq C_5 \leq \textcolor{red}{10^9}$.
  • $D_5$ is an integer satisfying $0 \leq D_5 \leq \textcolor{red}{10^9}$.

Output

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

Print a newline at the end.

Sample

Sample 1
Input
1 1 1
0 1
0 0
0 1
1 1
1 0
Output
0

Here $N = 1$, and initially we are given $A = (0 \cdot 1^0) = (0)$.

The $1$-st query $(i_1,j_1,x_1,y_1) = ((0 \cdot 0^0) \bmod N,(0 \cdot 1^0) \bmod N,1 \cdot 1^0,1 \cdot 0^0) = (0,0,1,1)$ replaces $A$ with

$\displaystyle (x_1) = (1) $

Then, for

$\displaystyle f(j_1,y_1) = f(0,1) = A_0 = 1 $

we print the remainder when divided by $B = 1$, which is $0$.

Since $Q = 1$, all queries have now been processed.

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

Here $N = 2$, and initially we are given $A = (1 \cdot 1^0,1 \cdot 1^1) = (1,1)$.

The $1$-st query $(i_1,j_1,x_1,y_1) = ((1 \cdot 0^0) \bmod N,(0 \cdot 1^0) \bmod N,1 \cdot 0^0,1 \cdot 0^0) = (1,0,1,1)$ replaces $A$ with

$\displaystyle (A_0,x_1) = (1,1) $

(resulting in no change). Then, for

$\displaystyle f(j_1,y_1) = f(0,1) = A_0 = 1 $

we print the remainder when divided by $B = 2$, which is $1$.

 

The $2$-nd query $(i_2,j_2,x_2,y_2) = ((1 \cdot 0^1) \bmod N,(0 \cdot 1^1) \bmod N,1 \cdot 0^1,1 \cdot 0^1) = (0,0,0,0)$ replaces $A$ with

$\displaystyle (x_2,A_1) = (0,1) $

Then, for

$\displaystyle f(j_2,y_2) = f(0,0) = A_0 = 0 $

we print the remainder when divided by $B = 2$, which is $0$.

Since $Q = 2$, all queries have now been processed.

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

Here $N = 4$, and initially we are given $A = (1 \cdot 2^0,1 \cdot 2^1,1 \cdot 2^2,1 \cdot 2^3) = (1,2,4,8)$.

The $1$-st query $(i_1,j_1,x_1,y_1) = ((2 \cdot 2^0) \bmod N,(3 \cdot 1^0) \bmod N,2 \cdot 1^0,2 \cdot 1^0) = (2,3,2,2)$ replaces $A$ with

$\displaystyle (A_0,A_1,x_1,A_3) = (1,2,2,8) $

Then, for

$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(3,2) \\ \displaystyle &\displaystyle = &\displaystyle 2 f(2,2) + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 f(0,2) + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 A_0 + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 \cdot 1 + 2 \cdot (2 + 2) + 8 \\ \displaystyle &\displaystyle = &\displaystyle 4 + 8 + 8 \\ \displaystyle &\displaystyle = &\displaystyle 20 \end{array} $

we print the remainder when divided by $B = 3$, which is $2$.

 

The $2$-nd query $(i_2,j_2,x_2,y_2) = ((2 \cdot 2^1) \bmod N,(3 \cdot 1^1) \bmod N,2 \cdot 1^1,2 \cdot 1^1) = (0,3,2,2)$ replaces $A$ with

$\displaystyle (x_2,A_1,A_2,A_3) = (2,2,2,8) $

Then, for

$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(3,2) \\ \displaystyle &\displaystyle = &\displaystyle 2^2 A_0 + 2 \sum_{i=0+1}^{2} A_i + \sum_{i=2+1}^{3} A_i \\ \displaystyle &\displaystyle = &\displaystyle 2^2 \cdot 2 + 2 \cdot (2 + 2) + 8 \\ \displaystyle &\displaystyle = &\displaystyle 8 + 8 + 8 \\ \displaystyle &\displaystyle = &\displaystyle 24 \end{array} $

we print the remainder when divided by $B = 3$, which is $0$.

Since $Q = 2$, all queries have now been processed.

Sample 4
Input
8 4 2
1 1
3 2
7 1
2 3
3 2
Output
3
3

Here $N = 8$, and initially we are given $A = (1 \cdot 1^0,1 \cdot 1^1,1 \cdot 1^2,1 \cdot 1^3,1 \cdot 1^4,1 \cdot 1^5,1 \cdot 1^6,1 \cdot 1^7) = (1,1,1,1,1,1,1,1)$.

The $1$-st query $(i_1,j_1,x_1,y_1) = ((3 \cdot 2^0) \bmod N,(7 \cdot 1^0) \bmod N,2 \cdot 3^0,3 \cdot 2^0) = (3,7,2,3)$ replaces $A$ with

$\displaystyle (A_0,A_1,A_2,x_1,A_4,A_5,A_6,A_7) = (1,1,1,2,1,1,1,1) $

Then, for

$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(7,3) \\ \displaystyle &\displaystyle = &\displaystyle 3 f(6,3) + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^2 f(4,3) + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 f(0,3) + 3^2 \sum_{i=0+1}^{4} A_i + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 A_0 + 3^2 \sum_{i=0+1}^{4} A_i + 3 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 3^3 \cdot 1 + 3^2 \cdot (1 + 1 + 2 + 1) + 3 \cdot (1 + 1) + 1 \\ \displaystyle &\displaystyle = &\displaystyle 27 + 45 + 6 + 1 \\ \displaystyle &\displaystyle = &\displaystyle 79 \end{array} $

we print the remainder when divided by $B = 4$, which is $3$.

 

The $2$-nd query $(i_2,j_2,x_2,y_2) = ((3 \cdot 2^1) \bmod N,(7 \cdot 1^1) \bmod N,2 \cdot 3^1,3 \cdot 2^1) = (6,7,6,6)$ replaces $A$ with

$\displaystyle (A_0,A_1,A_2,A_3,A_4,A_5,x_2,A_7) = (1,1,1,2,1,1,6,1) $

Then, for

$\displaystyle \begin{array}{rcl} \displaystyle f(j_1,y_1) &\displaystyle = &\displaystyle f(7,6) \\ \displaystyle &\displaystyle = &\displaystyle 6 f(6,6) + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^2 f(4,6) + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 f(0,6) + 6^2 \sum_{i=0+1}^{4} A_i + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 A_0 + 6^2 \sum_{i=0+1}^{4} A_i + 6 \sum_{i=4+1}^{6} A_i + \sum_{i=6+1}^{7} A_i \\ \displaystyle &\displaystyle = &\displaystyle 6^3 \cdot 1 + 6^2 \cdot (1 + 1 + 2 + 1) + 6 \cdot (6 + 1) + 1 \\ \displaystyle &\displaystyle = &\displaystyle 216 + 180 + 42 + 1 \\ \displaystyle &\displaystyle = &\displaystyle 439 \end{array} $

we print the remainder when divided by $B = 4$, which is $3$.

Since $Q = 2$, all queries have now been processed.

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