P8825正经题解

· · 题解

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

笔者自感跟大牛们的差距，于是去自学了一下数位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)，可以在三十至四十毫秒内轻松跑过。