P8825爆搜题解

Ja50nY0un9 · 2022-11-11 19:02:01 · 题解

chen_zhe 曾经在 P8438 的题解中说过，要对洛谷评测机的运算能力有高度了解。

那篇题解中说到洛谷评测机能每秒进行大概 1.2\times10^9 次 unsigned long long 的乘法运算。

于是笔者猜测计算 int 的取模虽然很慢但大概也慢不了多少。

于是就有了这篇完全不用数学方法的题解。

当然，用数位dp可以在多项式复杂度时间内跑过此题，在我的另一篇题解里面。

思路：

思路非常简单，就是运用 n 层 \operatorname{dfs} 暴力枚举出所有可能组出的数。

然后暴力判断是否可以被 k 整除，如果能整除就更新答案。

不开 O2 的情况下最大的点跑了 679 毫秒，还是挺快的。

不多哔哔，放代码。

搜索部分如下，通过代码在其基础上稍加调整即可，为了防止某些读者直接复制过去就不放了。

void dfs(int step, long long num){
    if (step > n){
        if (num % k == 0) cnt++;
        return;
    }
    num *= 10;
    for(int i = 1; i <= 6; i++)
        dfs(step + 1, num + i);
}

复杂度高达 \Theta(6^n) ，但最多取模次数仅仅有大约 6\times10^7 次，足以通过本题。

洛谷神机果然名不虚传。

至此，我们就用切一道红题的方法切掉了一道黄题。