問題一覧 > 通常問題

No.1025 Modular Equation

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : chocorusk / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 4031 / 自分の提出
問題文最終更新日: 2020-04-11 00:17:58
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 243 (順位表) の他の問題:

Problem Statement

You are given a prime $p$ and integers $a_1, a_2, \ldots , a_n$, $k$, $b$. How many tuples $(x_1, x_2, \ldots , x_n)$ of integers between $0$ and $p-1$, inclusive, are there such that the remainder when $a_1x_1^k+a_2x_2^k+\cdots +a_nx_n^k$ is divided by $p$ is $b$? Since the answer can be large, find it modulo $10^9+7$.

Input

$p\ n\ k\ b$
$a_1\ a_2\ \ldots\ a_n$

  • $2\leq p\leq 10^5$
  • $p$ is a prime.
  • $1\leq n\leq 500$
  • $1\leq k\leq 10^5$
  • $0\leq b\leq p-1$
  • $0\leq a_i\leq p-1$
  • All input values are integers.

Output

Print the number of tuples of integers satisfying the condition, modulo $10^9+7$.

Sample

Sample 1
Input
3 3 2 2
1 1 2
Output
6

There are $6$ tuples $(x_1, x_2, x_3)$ of integers between $0$ and $2$, inclusive, such that the remainder when $x_1^2+x_2^2+2x_3^2$ is divided by $3$ is $2$: $(0, 0, 1)$, $(0, 0, 2)$, $(1, 1, 0)$, $(1, 2, 0)$, $(2, 1, 0)$, $(2, 2, 0)$.

Sample 2
Input
7 5 3 6
3 1 4 1 5
Output
2373

Sample 3
Input
10007 1 314 159
0
Output
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。