No.1025 Modular Equation
タグ : / 解いたユーザー数 11
作問者 :
chocorusk
/ テスター :
tempura_pp
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もしくは右上の雲マークをクリックしてアカウントを作成してください。