[Link] https://AtCoder.jp/contests/typical90/tasks/typical90_e
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.*;
import java.io.*;
public class Main {
static int con = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long n;
int b, k, ans = 0;
int[] dp;
n = Long.parseLong(st.nextToken());
b = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
dp = new int[b];
for(int i = 0; i < k; i++) dp[Integer.parseInt(st.nextToken()) % b] += 1;
int[][] op = new int[b][b];
for(int i = 0; i < b; i++) {
for(int j = 0; j < b; j++) {
if(dp[j] == 0) continue;
int idx = (10 * i + j) % b;
op[idx][i] = dp[j];
}
}
long[][] finalOp = new long[b][b];
for(int i = 0; i < b; i++) finalOp[i][i] = 1;
// ArrayList<int[][]> al = new ArrayList<>();
// al.add(0, op); // 2^i;
long[][] temp = new long[b][b];
for(int i = 0; i < b; i++) for(int j = 0; j < b; j++) temp[i][j] = op[i][j];
int curIdx = 0;
boolean determined = false;
long v = 1;
int idx = 0;
n--;
while(n > 0) {
if(n % 2 == 1) {
if(idx > curIdx) {
for(int i = curIdx + 1; i <= idx; i++) {
temp = sqr(temp);
}
curIdx = idx;
}
finalOp = mul(finalOp, temp);
}
n = n >> 1;
idx++;
}
long ans1 = 0;
for(int i = 0; i < b; i++) {
ans1 += finalOp[0][i] * dp[i];
ans1 %= con;
}
System.out.println(ans1);
}
static long[][] mul(long[][] a, long[][] b) {
int len = b.length;
long[][] ans = new long[a.length][b[0].length];
for(int i = 0, la = a.length; i < la; i++) {
for(int j = 0, lb = b[0].length; j < lb; j++) {
for(int k = 0; k < len; k++) {
ans[i][j] += a[i][k]*b[k][j];
ans[i][j] %= con;
}
}
}
return ans;
}
static long[] mul(long[][] a, int[] b) {
long[] ans = new long[b.length];
for(int i = 0, la = a.length; i < la; i++) {
for(int j = 0, lab = b.length; j < lab; j++) {
ans[i] += a[i][j] * b[j];
ans[i] %= con;
}
}
return ans;
}
static long[][] sqr(long[][] a) {
return mul(a, a);
}
}