[LibreOJ 6059][2017 山东一轮集训 Day1] Sum

发表于2017-06-30更新于2020-08-06

题目大意

求有多少 nn 位十进制数是 pp 的倍数且每位之和小于等于 mi(mi=0,1,2,…,m−1,m)m_i (m_i = 0, 1, 2, \ldots, m - 1, m)，允许前导 00，答案对 998244353998244353 取模。

1⩽n⩽1,000,000,0001 \leqslant n \leqslant 1,000,000,000

1⩽q⩽501 \leqslant q \leqslant 50

1⩽m⩽1,0001 \leqslant m \leqslant 1,000

题目链接

LibreOJ 6059

题解

考虑 DP，记 f(i,j,k)f(i, j, k) 表示已经考虑了 ii 位、已经考虑的位数组成的数模 pp 的余数为 jj、已经考虑的位数的数字和为 kk 时的答案，则转移：

f(i,j,k)→f(i+1,(j×10+c) mod p,k+c)c=0,1,2…9f(i, j, k) \rightarrow f(i + 1, (j \times 10 + c) \bmod p, k + c) \quad c = 0, 1, 2 \dots 9

这样显然会 TLE。

转移可写为：

f(i,(j×10+c) mod p,k)=∑t=0kf(i−1,j,t)×f(1,c,k−t)f(i, (j \times 10 + c) \bmod p, k) = \sum_{t = 0}^{k} f(i - 1, j, t) \times f(1, c, k - t)

发现是卷积的形式。同时发现 DP 可以倍增。于是 FFT／NTT + 倍增 + DP 的解就出来了。

代码

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 <cstdio>
#include <algorithm>
const int MAXP = 50;
const int MAXM = 1000;
const int MAXM_EXTEND = 2048;
const int MOD = 998244353;
const int G = 3;
void exgcd(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;
}