問題一覧 > 通常問題

No.2506 Sum of Weighted Powers

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : suisen / テスター : emthrm torisasami4 rniya
お気に入りにしたユーザー ProblemId : 9372 / 自分の提出
問題文最終更新日: 2023-07-13 19:26:13
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 408 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。