【题解】Sum NTT 优化转移 loj6059 ——quhengyi11

传送喵

因为机房快要关门了所以我们直接跳到第六段 (雾)

我们记 $f[i][j][k]$，表示 $i$位数，模 $p=j$，和 $=k$的方案数

我们有

$$f[x+y][(j1 \times w + j2)\%p][k1+k2]=f[x][j1][k1]\times f[y][j2][k2]$$
其中 $w=pow(10,k2)\% p$

发现这是一个卷积的形式，我们可以把转移用 $NTT$加速

具体来讲就是记 $f[i][j]$表示当前模 $p=i$，和 $=j$的方案数。

然后我们双重暴力枚举 $i$，再把它像上面那个转移方程一样卷积起来。

我们可以将 $solve()$写成类似快速幂的形式，每次自己和自己通过上面的过程卷积，如果有奇数次幂的话，暴力乘就行，就是一个常数。

#include<bits/stdc++.h>
#define N 3000005
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define Re register
#define mod 998244353
#define M 1033
#define ll long long
const double pi = acos(-1);
int n, m, R[N], L, len, invlen, p;
ll c1[N], c2[N], w[N], ans[N], iw[N];
inline ll pow (ll x, int y, int Mo)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % Mo;
        x = x * x % Mo;
        y >>= 1;
    }
    return ret;
}
inline void init ()
{
    len = 1;
    while (len <= m + m) len = len << 1, ++L;
    invlen = pow(len, mod - 2, mod);
    for (int i = 0; i < len; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L - 1); 
    w[0] = 1; w[1] = pow(3, (mod - 1) / len, mod);
    for (int i = 2; i < len; ++i) w[i] = w[i - 1] * w[1] % mod;
    iw[0] = 1; iw[1] = pow(w[1], mod - 2, mod);
    for (int i = 2; i < len; ++i) iw[i] = iw[i - 1] * iw[1] % mod;
}
inline void ntt (ll *c, bool opt)
{
    for (int i = 0; i < len; ++i) if (i < R[i]) std::swap(c[i], c[R[i]]);
    for (int l = 2; l <= len; l <<= 1)
    {
        int mid = l >> 1, now = len / l;
        for (ll *p = c; p != c + len; p += l)
            for (Re int i = 0; i < mid; ++i)
            {
                ll tmp = (opt ? w[now * i] : iw[now * i]) * p[mid + i] % mod;
                p[mid + i] = (p[i] - tmp) % mod;
                p[i] = (p[i] + tmp) % mod;
            }
    }
}
ll f[55][M << 1], g[55][M << 1];
inline void solve (int n)
{
    if (n == 1)
    {
        for (int i = 0; i < 10 && i <= m; ++i) f[i % p][i] = 1;
        return;
    }
    solve(n >> 1);
    memcpy(g, f, sizeof g);
    memset(f, 0, sizeof f);
    for (int i = 0; i < p; ++i) ntt(g[i], 1);
    ll w = pow(10, n >> 1, p);
    for (int i = 0; i < p; ++i)
        for (int j = 0; j < p; ++j)
            for (int k = 0; k < len; ++k)
                (f[(i * w + j) % p][k] += g[i][k] * g[j][k] % mod) %= mod;
    for (int i = 0; i < p; ++i)
    {
        ntt(f[i], 0);
        fo (j, 0, m) (f[i][j] *= invlen) %= mod;
        fo (j, m + 1, len) f[i][j] = 0;
    }
    if (n & 1)
    {
        memcpy(g, f, sizeof g);
        memset(f, 0, sizeof f);
        for (int i = 0; i < p; ++i)
            for (int j = 0; j < 10; ++j)
                fo (k, j, m)
                    (f[(i * 10 + j) % p][k] += g[i][k - j]) %= mod;
    }
}
int main()
{
    scanf("%d %d %d", &n, &p, &m);
    init();
    solve(n);
    fo (i, 1, m) (f[0][i] += f[0][i - 1]) %= mod;
    fo (i, 0, m) printf("%lld ", (f[0][i] + mod) % mod);
}