No.1025 Modular Equation
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 :
chocorusk
/ テスター :
tempura_pp
タグ : / 解いたユーザー数 10
作問者 :
chocorusk
/ テスター :
tempura_pp
問題文最終更新日: 2020-04-11 00:17:58
問題文
素数 $p$ と整数 $a_1, a_2, \ldots , a_n$, $k$, $b$ が与えられます。$a_1x_1^k+a_2x_2^k+\cdots +a_nx_n^k$ を $p$ で割った余りが $b$ であるような、$0$ 以上 $p-1$ 以下の整数の組 $(x_1, x_2, \ldots , x_n)$ は何個あるでしょうか。答えは大きくなりうるので、$10^9+7$ で割った余りを求めてください。
入力
$p\ n\ k\ b$ $a_1\ a_2\ \ldots\ a_n$
- $2\leq p\leq 10^5$
- $p$ は素数である。
- $1\leq n\leq 500$
- $1\leq k\leq 10^5$
- $0\leq b\leq p-1$
- $0\leq a_i\leq p-1$
- 入力はすべて整数である。
出力
条件を満たす整数の組の個数を $10^9+7$ で割った余りを出力せよ。
サンプル
サンプル1
入力
3 3 2 2 1 1 2
出力
6
$x_1^2+x_2^2+2x_3^2$ を $3$ で割った余りが $2$ であるような $0$ 以上 $2$ 以下の整数の組 $(x_1, x_2, x_3)$ は、$(0, 0, 1)$, $(0, 0, 2)$, $(1, 1, 0)$, $(1, 2, 0)$, $(2, 1, 0)$, $(2, 2, 0)$ の $6$ 通りです。
サンプル2
入力
7 5 3 6 3 1 4 1 5
出力
2373
サンプル3
入力
10007 1 314 159 0
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。