No.8112 Polynomial with Range Sum Coefficients?
タグ : / 解いたユーザー数 5
作問者 : 👑
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:
- First, update $A$ by replacing $A_i$, the $1 + i$-th element of $A$, with $x$.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。