自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

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

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

以下是正文

---

$$\color{Orange}\sf dWoi\ Round\ 1\ B\ Password\ of\ Shady $$

Description

求有多少个 $n$ 位无前导零的数满足所有数位中有偶数个 $k$。
$1 \le n \le 10^5$，$1 \le k \le 9$，$1 \le t \le 10^6$

Subtask 1

约束条件：$n=1$。

一位数只有 $0 \sim 9$，$1 \le k \le 9$，所以肯定输出 $9$。

Subtask 2

约束条件：$n \le 6$。

留给了爆搜或者写挂没开 long long 的正解。

然后发现暴力貌似是 $\mathcal O(t9^n)$ 或者 $\mathcal O(t+9^n)$ 的

Subtask 3

约束条件：$t \le 10^5$。

考虑动态规划。

对于一个满足要求的 $i$ 位数，可以由一个不满足要求的 $i-1$ 位数加上一位 $k$ 或者由一个满足要求的 $i-1$ 位数加上一位除了 $k$ 之外的数位得来，同理，对于一个不满足要求的 $i$ 位数，可以由一个满足要求的 $i$ 位数加上一位 $k$ 或者由一个不满足要求的 $i-1$ 位数加上一位除了 $k$ 之外的数得来。

因此我们可以开两个数组 $f[i],g[i]$，$f[i]$ 构造满足要求的 $i$ 位数，$g[i]$ 构造不满足要求的 $i$ 位数，按照我们上面分析的，转移方程也就出来了：

$$f[i]=f[i-1] \times 9+g[i-1]$$ $$g[i]=g[i-1] \times 9+f[i-1]$$

对于初值，注意特判 $0$，$f[1]=8,g[1]=1$。

另外，$n=1$ 时也要特判。

然后你就得到了 $\mathcal O(tn)$ 的优秀解法，但并 A 不了。

你也可以尝试矩阵快速幂，听 lgd 说是 $\mathcal O(t \log n)$，但好像也 A 不了。

Subtask 4

考虑初始化，把 $1 \sim 10^5$ 的答案提前初始化到输出 $ans[i]$ 里，然后每次循环输入 $n$ 直接输出 $ans[n]$ 即可。

然后你就得到了 $\mathcal O(t+n)$ 的优秀 AC 做法。

Code

#include <bits/stdc++.h>

using namespace std;

unsigned long long f[100005];
unsigned long long g[100005];

int main () {
    int t;
    scanf("%d", &t);
    f[1] = 8, g[1] = 1;
    for (int i = 2; i <= 100000; i++) {
        f[i] = f[i - 1] * 9 + g[i - 1];
		g[i] = g[i - 1] * 9 + f[i - 1];
        f[i] %= 998244353;
        g[i] %= 998244353;
    }
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        if (n == 1) {
            puts("9");
            continue;
        }
        printf("%llu\n", f[n] % 998244353);
        continue;
    }
    return 0;
}