dWoi Round 1 B 题解

一只书虫仔 · 2020-11-08 13:28:27 · 题解

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 位数，按照我们上面分析的，转移方程也就出来了：

对于初值，注意特判 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;
}