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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#include <algorithm>
const int MAXP = 50;
const int MAXM = 1000;
const int MAXM_EXTEND = 2048;
const int MOD = 998244353;
const int G = 3;
void (long long a, long long b, long long &x, long long &y) {
if (!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= x * (a / b);
}
long long inv(long long x) {
long long res, temp;
exgcd(x, MOD, res, temp);
return (res + MOD) % MOD;
}
long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}
namespace NumberTheoreticTransform {
static const int N = 2048;
long long omega[N], omegaInv[N];
void init() {
long long g = pow(G, (MOD - 1) / N), ig = inv(g);
omega[0] = omegaInv[0] = 1;
for (int i = 1; i < N; i++) {
omega[i] = omega[i - 1] * g % MOD;
omegaInv[i] = omegaInv[i - 1] * ig % MOD;
}
}
int extend(int n) {
int res = 1;
while (res < n) res <<= 1;
return res;
}
void reverse(long long *a, int n) {
int k = 0;
while ((1 << k) < n) k++;
for (int i = 0, j = 0; i < n; i++) {
if (i < j) std::swap(a[i], a[j]);
for (int l = n >> 1; (j ^= l) < l; l >>= 1);
}
}
void transform(long long *a, int n, long long *omega) {
reverse(a, n);
for (int l = 2; l <= n; l <<= 1) {
int hl = l >> 1;
for (long long *x = a; x != a + n; x += l) {
for (int i = 0; i < hl; i++) {
long long t = omega[N / l * i] * x[i + hl] % MOD;
x[hl + i] = (x[i] - t + MOD) % MOD;
(x[i] += t) %= MOD;
}
}
}
}
void dft(long long *a, int n) {
transform(a, n, omega);
}
void idft(long long *a, int n) {
transform(a, n, omegaInv);
long long t = inv(n);
for (int i = 0; i < n; i++) (a[i] *= t) %= MOD;
}
}
int p, m;
struct Data {
long long pow, a[MAXP][MAXM_EXTEND];
Data() : pow(1), a() {}
};
Data operator*(Data &a, Data &b) {
Data res;
res.pow = a.pow * b.pow % p;
int s = NumberTheoreticTransform::extend(m + 1) * 2;
for (int i = 0; i < p; i++) {
NumberTheoreticTransform::dft(a.a[i], s);
if (&a != &b) NumberTheoreticTransform::dft(b.a[i], s);
}
for (int i1 = 0; i1 < p; i1++) for (int i2 = 0; i2 < p; i2++) {
static long long temp[MAXM_EXTEND];
for (int i = 0; i < s; i++) temp[i] = a.a[i1][i] * b.a[i2][i];
NumberTheoreticTransform::idft(temp, s);
for (int i = 0; i <= m; i++) (res.a[(i1 * b.pow + i2) % p][i] += temp[i]) %= MOD;
}
for (int i = 0; i < p; i++) {
NumberTheoreticTransform::idft(a.a[i], s);
if (&a != &b) NumberTheoreticTransform::idft(b.a[i], s);
}
return res;
}
Data pow(Data a, int n) {
Data res;
res.a[0][0] = 1;
for (; n; n >>= 1, a = a * a) if (n & 1) res = res * a;
return res;
}
int main() {
NumberTheoreticTransform::init();
int n;
scanf("%d %d %d", &n, &p, &m);
Data init;
init.pow = 10;
for (int i = 0; i <= std::min(9, m); i++) init.a[i % p][i]++;
Data res = pow(init, n);
long long ans = 0;
for (int i = 0; i <= m; i++) {
(ans += res.a[0][i]) %= MOD;
printf("%lld%c", ans, " n"[i == m]);
}
return 0;
}
|
近期评论