P9006 [入门赛 #9] 神树大人挥动魔杖 (hv)

· · 题解

看了题解区各位大神的题解，蒟蒻表示看不懂，于是写一篇详细易懂的题解。

Analysis

我们需要求所有 n 位数中模 k 余 r 的有多少个，这句话一出暴力思路就出来了。

那么想怎么不枚举所有数，可以发现当前的数可以是上一个数加一位数得来的，而假如以前的余数是 r，加一位数字 d，那么新余数 r'=(10r+d) \bmod k，这两个条件指向了同一个方法动态规划。

定义 f_{m,r} 表示长度为 m 的数字串（首位可以为 0）模 k 余 r 的个数。这样递推更容易，因为只关心长度和余数。初始条件 f_{1,r} 枚举一遍算出答案。根据上述 r'=(10r+d) \bmod k，对于每个 r：

f_{m+1,r'} \leftarrow f_{m+1,r'}+f_{m,r}

现在看问题，对于所有 0 \le r \le k-1，求出长度为 n 且首位不为 0 的数中，模 k 余 r 的个数，就设它为 g_{n,r}。

那么首位从 1 \sim 9 选，后面 n-1 位可以任意，已经用 f 算好了。首位 d_1 对整个数余数的贡献是 d_1 \times 10^{n-1} \bmod k，若后面 n-1 位余数记为 r'，则整体余数 r=(d_1 \times 10^{n-1} + r') \bmod k。

所以对给定的 r 和 d_1，需要 r' \equiv r - d_1 \times 10^{n-1} \ (\bmod \ k)。设 base = d_1 \times 10^{n-1} \bmod k，于是：

g_{n,r}=\sum_{d_1=1}^{9} f_{n-1,(r-base+k) \bmod k}

最后注意 n=1 特判，注意模数 10^8+7。时间复杂度 \Theta(nk)。

::::success[Code] 我使用了 vector 和空行让代码看起来更舒服。

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

const int mod = 1e8 + 7;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n, k;
    cin >> n >> k;

    int p10 = 1;
    for(int i = 1; i < n; ++ i)
        p10 = (p10 * 10) % k;

    vector<vector<int> > f(n + 1, vector<int>(k, 0));
    for(int d = 0; d <= 9; ++ d)
        ++ f[1][d % k];
    for(int m = 2; m < n; ++ m)
        for(int rp = 0; rp < k; ++ rp){
            if(f[m - 1][rp] == 0)
                continue;
            int t = rp * 10 % k;
            for(int d = 0; d <= 9; ++ d){
                int rn = (t + d) % k;
                f[m][rn] = (f[m][rn] + f[m - 1][rp]) % mod;
            }
        }

    if(n == 1){
        for(int r = 0; r < k; ++ r){
            int cnt = 0;
            for(int d = 1; d <= 9; ++ d)
                if(d % k == r)
                    ++ cnt;
            cout << cnt % mod << " ";
        }
        return 0;
    }

    vector<int> ans(k, 0);
    for(int d = 1; d <= 9; ++ d){
        int base = d * p10 % k;
        for(int r = 0; r < k; ++ r){
            int nr = (r - base + k) % k;
            ans[r] = (ans[r] + f[n - 1][nr]) % mod;
        }
    }

    for(int r = 0; r < k; ++ r)
        cout << ans[r] << " ";

    return 0;
}

::::

Thanks.