No.2506 Sum of Weighted Powers
タグ : / 解いたユーザー数 12
作問者 :
suisen
/ テスター :
👑 
emthrm
torisasami4
rniya
問題文
長さ $n + 1$ の整数列 $A = (A _ 0, A _ 1, \ldots, A _ n),\ B = (B _ 0, B _ 1, \ldots, B _ n),\ C = (C _ 0, C _ 1, \ldots, C _ n)$ と整数 $x$ が与えられます。
整数の組 $(i, j, k)$ であって、以下の条件を全て満たすもの全体の集合を $\Lambda _ n$ とします。
- $0 \leq i\leq n$
- $0 \leq j\leq n$
- $0 \leq k\leq n$
- $i = j + k$
以下で定義される整数 $S$ を $\mathbf{\color{red}{943718401}}$ で割った余りを求めてください。
$$S \coloneqq \sum _ {(i, j, k) \in \Lambda _ n} A _ i B _ j C _ k x ^ {ijk}.$$
ただし、本問題では $0 ^ 0 = 1$ と定義します。
入力
入力は標準入力から以下の形式で与えられます。
$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}$
- 入力は全て整数で与えられる。
- $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$
出力
$1$ 行目に $S$ を $\mathbf{\color{red}{943718401}}$ で割った余りを出力してください。最後に改行してください。
通常とは異なる mod に注意してください。
サンプル
サンプル1
入力
2 6 1 2 3 4 5 6 7 8 9
出力
4716
この入力は $n = 2,\ x = 6,\ A = (1,2,3),\ B = (4,5,6),\ C = (7,8,9)$ を表します。
$n = 2$ なので、$\Lambda _ n = \lbrace (0,0,0),(1,0,1),(1,1,0),(2,0,2),(2,1,1),(2,2,0) \rbrace$ です。各 $(i, j, k)\in \Lambda _ n$ に対して $A _ i B _ j C _ k x ^ {ijk}$ は次のように計算されます。
- $(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$
- $(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$
- $(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$
- $(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$
- $(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$
- $(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$
従って、$S = 28 + 64 + 70 + 108 + 4320 + 126 = 4716$ です。
サンプル2
入力
6 8 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6
出力
577188643
$S = 175381980539324232634621556894490491241691423184779$ ですが、$S$ を $\mathbf{\color{red}{943718401}}$ で割った余りである $577188643$ を出力する必要があります。
サンプル3
入力
0 10 10 10 10
出力
1000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。