「dWoi R1」Password of Shady

题意

给出 t 组询问，每组给 n, k。

要求统计有多少个满足条件的 n 位数：

没有前导零；
数位中数字 k 出现了偶数次。

答案对 998244353 取模。

思路

最直接的办法是枚举所有合法的 n 位数，再统计其中数字 k 出现次数是不是偶数。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <bits/stdc++.h>
using namespace std;

// brute.cpp：暴力枚举所有合法 n 位数，统计其中 digit k 出现次数为偶数的数量。

const int MOD = 998244353;

int t;
int n, k;
int ans;

void dfs(int pos, int parity) {
    if (pos > n) {
        if (parity == 0) {
            ans++;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
        return;
    }

    int start = 0;
    if (n > 1 && pos == 1) {
        start = 1;
    }

    for (int digit = start; digit <= 9; digit++) {
        int next_parity = parity;
        if (digit == k) {
            next_parity ^= 1;
        }
        dfs(pos + 1, next_parity);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> n >> k;
        ans = 0;
        dfs(1, 0);
        cout << ans << '\n';
    }

    return 0;
}

这份暴力代码显然只能做很小的数据，因为合法数大约有 $9 * 10^(n-1)$ 个。

这题真正的关键观察是：k 的具体值根本不重要。

无论 $k = 1$ 还是 $k = 9$ ，对于每一位来说都只有两类数字：

1 个特殊数字：k
9 个普通数字：不是 k

所以我们完全不需要关心 k 的具体值，只需要关心“当前出现了奇数个还是偶数个 k”。

设：

even：当前长度下，数字 k 出现偶数次的方案数
odd：当前长度下，数字 k 出现奇数次的方案数

先看长度至少为 2 的情况。因为首位不能为 0，第一位只有 $1 \dots 9$ 这 9 个选择：

填 k：1 种，进入奇数状态
填 $1 \dots 9$ 中除 k 外的数字：8 种，进入偶数状态

所以初始值是：

$even = 8$
$odd = 1$

之后每增加一位：

填的不是 k：有 9 种，奇偶性不变
填的是 k：有 1 种，奇偶性翻转

于是转移为：

$new_even = even * 9 + odd$
$new_odd = even + odd * 9$

状态表

这张表展示前几位时两种状态数量的变化：

长度	偶数态 `even`	奇数态 `odd`
1（首位）	`8`	`1`
2	`73`	`17`
3	`674`	`226`

表中长度 2 时的偶数态就是样例第一组答案 73。因为我们只是在统计“奇偶状态的方案数”，而不是枚举具体数字，所以可以在线性时间预处理出所有长度答案。

最后只要注意一个边界：

当 $n = 1$ 时，一位数可以是 $0 \dots 9$
只有数字 k 本身会让出现次数变成 1

所以 $n = 1$ 的答案是 9。

预处理完 ans[n] 后，每次询问直接输出即可，复杂度是 $O(1)$ 。

DP 公式

设 $even_i$ 表示长度为 $i$ 且数字 $k$ 出现偶数次的方案数， $odd_i$ 表示出现奇数次的方案数。首位不能为 $0$ ，所以：

even_1=8,\quad odd_1=1

当 $i>1$ 时：

even_i=9\cdot even_{i-1}+odd_{i-1}

odd_i=even_{i-1}+9\cdot odd_{i-1}

答案为 $even_n$ 。特殊地， $n=1$ 时允许数字 $0$ ，答案是：

ans_1=9

公式解释：状态只记录数字 k 出现次数的奇偶性。新填一位不是 k 时奇偶性不变，有 9 种选择；新填一位是 k 时奇偶性翻转，有 1 种选择。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const int MOD = 998244353;

int t;
int ans[MAXN + 5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // n = 1 时，一位数可以是 0~9，共 10 个。
    // 因为 k 在 1~9 中，只有数字 k 本身会出现 1 次，所以合法数有 9 个。
    ans[1] = 9;

    // 下面维护“长度至少为 1，且首位已经确定为非 0”时的奇偶状态。
    // len = 1 时：
    // - 偶数个 k：首位不是 k，有 8 种
    // - 奇数个 k：首位是 k，有 1 种
    long long even = 8;
    long long odd = 1;

    for (int len = 2; len <= MAXN; len++) {
        long long new_even = (even * 9 + odd) % MOD;
        long long new_odd = (even + odd * 9) % MOD;
        even = new_even;
        odd = new_odd;
        ans[len] = (int)even;
    }

    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << ans[n] << '\n';
    }

    return 0;
}

复杂度

预处理复杂度： $O(max_n)$
单次询问复杂度： $O(1)$
空间复杂度： $O(max_n)$

总结

这题表面上是“统计某个数字出现偶数次”的计数题，真正的突破口是把它压缩成“奇数态 / 偶数态”两种状态。

一旦看出 k 的具体值不重要，整题就变成非常短的按位递推。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。