自动搬运

查看原文

来自洛谷，原作者为

	Ja50nY0un9 感觉不如化学（？

搬运于2025-08-24 22:42:52，当前版本为作者最后更新于2022-11-13 09:37:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

想必看到这篇题解的人也看过这个碰运气通过了的暴力搜索做法吧。

笔者自感跟大牛们的差距，于是去自学了一下数位dp，自认为弄懂了，就有了这篇题解。

思路：

因为前面的掷骰不会对之后有所影响，如上所述，考虑数位dp。

我们用 $f_{i,j}$ 表示选到第 $i$ 个数，模 $k$ 余 $j$ 的方法数。

显然，每一个 $f_{i,j}$ 因为在原来的基础上数位增加了一位，所以其余数就增加到了原来的十倍。

那么我们就可以得到转移方程：

f[i][(l * 10 + j) % k] += f[i - 1][l];

此处 $j$ 枚举的是本次掷出的数，而 $l$ 枚举的是上一次掷骰后构成的数模 $k$ 的余数。

初始状态是，我们在什么都没有掷的时候，模 $k$ 显然只能余 $0$，此时方案为一种。

所以，初始状态是 $f[0][0]=1$。

都想到了这里，想必代码实现就不是问题了。

为了防止有些人无脑复制，我就只放上dp初始化和转移部分的代码吧。

f[0][0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 6; j++)
        for (int l = 0; l < k; l++){
            f[i][(l * 10 + j) % k] += f[i - 1][l];
        }
cout << f[n][0];

至此，我们就通过数位dp拿到了本道题的正解。

这篇题解的方法就不用卡时了，复杂度 $\Theta(nk)$，可以在三十至四十毫秒内轻松跑过。