/
1025.test.cpp
61 lines (53 loc) · 1.09 KB
/
1025.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define PROBLEM "https://yukicoder.me/problems/no/1025"
#include "my_template.hpp"
#include "other/io.hpp"
#include "mod/modint.hpp"
#include "mod/primitive_root.hpp"
using mint = modint107;
void solve() {
LL(p, n, k, b);
const int g = primitive_root(p);
vc<int> EXP(p - 1);
vc<int> LOG(p);
{
EXP[0] = 1;
FOR(i, p - 2) EXP[i + 1] = EXP[i] * ll(g) % p;
FOR(i, p - 1) LOG[EXP[i]] = i;
}
k = gcd(k, p - 1);
vc<int> root(p);
FOR(x, 1, p) {
int e = LOG[x];
e %= k;
root[x] = EXP[e];
}
vc<int> S;
FOR(i, 0, p - 1, k) S.eb(EXP[i]);
vc<int> B;
FOR(v, p) if (root[v] == v) B.eb(v);
vc<mint> dp(p);
dp[0] = mint(1);
FOR(n) {
LL(a);
vc<mint> newdp = dp;
for (auto&& s: S) {
int t = s * a % p;
for (auto&& x: B) {
int to = x + t;
if (to >= p) to -= p;
newdp[root[to]] += dp[x] * mint(k);
}
}
swap(dp, newdp);
}
mint ANS = dp[root[b]];
if (b != 0) ANS /= mint(len(S));
print(ANS);
}
signed main() {
cout << fixed << setprecision(15);
ll T = 1;
// LL(T);
FOR(T) solve();
return 0;
}