神树大人挥动魔杖

览遍千秋 · 2023-02-06 00:16:44 · 题解

Solution

递推。

记 f(i,j) 代表所有的 i 位数，对 k 取模余 j 的数目。

枚举 i 位数最高位上填的数 p，显然有 p = 1, 2, \cdots ,9。

很容易求出 p \times 10^{i-1} 对 k 取模的值，记为 R。

则 f(i,j)=\sum\limits_{a=1}^{i=1}f(a,(j-R) \bmod k)。

对于每一个 j，前缀和累加 f(i,j) 即可，时间复杂度为 O(nk)。

需要注意的是，答案模数为 100000007，即 10^8+7，一个优秀的 OIer 是会数数字位数的。

Codes

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5000 + 7;
const int MAXK = 1000 + 7;
const int mod = 100000007; 

int n, k;
long long f[MAXN][MAXK];
long long sum[MAXK];

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 9; i++) f[1][i % k]++, sum[i % k]++;
    if(n == 1) {
        for(int i = 0; i < k; i++) {
            printf("%lld%c", f[n][i], " \n"[i == k - 1]);
        }
        return 0;
    }

    long long mul = 1;
    for(int i = 2; i <= n; i++) {
        mul = mul * 10 % k;
        for(int j = 1; j <= 9; j++) {
            long long val = j * mul % k;
            for(int p = 0; p < k; p++) {
                long long to = (p + val) % k;
                f[i][to] = (f[i][to] + sum[p]) % mod;
            }
            f[i][val]++;
        }
        for(int j = 0; j < k; j++) sum[j] += f[i][j], sum[j] %= mod;
    }
    for(int i = 0; i < k; i++) {
        printf("%lld%c", f[n][i], " \n"[i == k - 1]);
    }
    return 0;
}