No.2506 Sum of Weighted Powers
タグ : / 解いたユーザー数 14
作問者 :
emthrm
torisasami4
rniya
Problem Statement
You are given integer sequences $A = (A _ 0, A _ 1, \ldots, A _ n),\ B = (B _ 0, B _ 1, \ldots, B _ n),\ C = (C _ 0, C _ 1, \ldots, C _ n)$ of length $n + 1$ and an integer $x$.
Let $\Lambda _ n$ be the set of all integer triples $(i, j, k)$ satisfying all of the following conditions.
- $0 \leq i\leq n$
- $0 \leq j\leq n$
- $0 \leq k\leq n$
- $i = j + k$
Find the remainder when the integer $S$ defined below is divided by $\mathbf{\color{red}{943718401}}$.
$$S \coloneqq \sum _ {(i, j, k) \in \Lambda _ n} A _ i B _ j C _ k x ^ {ijk}.$$
Here, in this problem, we define $0 ^ 0 = 1$.
Input
The input is given from Standard Input in the following format.
$n\ x$
$\begin{alignedat}{4}
&A_0 &\ & A_1 &\ & \cdots &\ & A_n \newline
&B_0 &\ & B_1 &\ & \cdots &\ & B_n \newline
&C_0 &\ & C_1 &\ & \cdots &\ & C_n \newline
\end{alignedat}$
- All input values are integers.
- $0\leq n\leq 2 \times 10 ^ 5$
- $0\leq x\lt 943718401$
- $0\leq A_i\lt 943718401$
- $0\leq B_i\lt 943718401$
- $0\leq C_i\lt 943718401$
Output
Print on line $1$ the remainder when $S$ is divided by $\mathbf{\color{red}{943718401}}$. End the output with a newline.
Note that the modulus differs from the usual one.
Sample
Sample 1
Input
2 6 1 2 3 4 5 6 7 8 9
Output
4716
This input represents $n = 2,\ x = 6,\ A = (1,2,3),\ B = (4,5,6),\ C = (7,8,9)$.
Since $n = 2$, we have $\Lambda _ n = \lbrace (0,0,0),(1,0,1),(1,1,0),(2,0,2),(2,1,1),(2,2,0) \rbrace$. For each $(i, j, k)\in \Lambda _ n$, $A _ i B _ j C _ k x ^ {ijk}$ is calculated as follows.
- For $(i,j,k)=(0,0,0)$, $A _ 0 B _ 0 C _ 0 x ^ {0\cdot 0\cdot 0} = 1\cdot 4\cdot 7 \cdot 6 ^ 0 = 28$
- For $(i,j,k)=(1,0,1)$, $A _ 1 B _ 0 C _ 1 x ^ {1\cdot 0\cdot 1} = 2\cdot 4\cdot 8 \cdot 6 ^ 0 = 64$
- For $(i,j,k)=(1,1,0)$, $A _ 1 B _ 1 C _ 0 x ^ {1\cdot 1\cdot 0} = 2\cdot 5\cdot 7 \cdot 6 ^ 0 = 70$
- For $(i,j,k)=(2,0,2)$, $A _ 2 B _ 0 C _ 2 x ^ {2\cdot 0\cdot 2} = 3\cdot 4\cdot 9 \cdot 6 ^ 0 = 108$
- For $(i,j,k)=(2,1,1)$, $A _ 2 B _ 1 C _ 1 x ^ {2\cdot 1\cdot 1} = 3\cdot 5\cdot 8 \cdot 6 ^ 2 = 4320$
- For $(i,j,k)=(2,2,0)$, $A _ 2 B _ 2 C _ 0 x ^ {2\cdot 2\cdot 0} = 3\cdot 6\cdot 7 \cdot 6 ^ 0 = 126$
Therefore, $S = 28 + 64 + 70 + 108 + 4320 + 126 = 4716$.
Sample 2
Input
6 8 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6
Output
577188643
$S = 175381980539324232634621556894490491241691423184779$, but you must print $577188643$, the remainder when $S$ is divided by $\mathbf{\color{red}{943718401}}$.
Sample 3
Input
0 10 10 10 10
Output
1000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。