No.1025 Modular Equation

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 7
作問者 : chocoruskchocorusk / テスター : tempura_pptempura_pp
2 ProblemId : 4031 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。