蓝桥杯 2023年省赛真题
^{C/C++ 大学G组}

 试题 A: 工作时长
 试题 B: 与或异或
 试题 C: 翻转
 试题 D: 阶乘的和
 试题 E: 公因数匹配
 试题 F: 奇怪的数
 试题 G: 太阳
 试题 H: 子树的大小
 试题  I: 高塔
 试题 J: 反异或 01 串

---

除去第 $\mathrm{F}$ 题，其他题目在其他组别都有出现过，这里就不重写了。

---

奇怪的数

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$15$ 分

---

【问题描述】

  小蓝最近在找一些奇怪的数，其奇数数位上是奇数，而偶数数位上是偶数。同时，这些数的任意 $5$ 个连续数位的和都不大于 $m$。
  例如当 $m=9$ 时，$10101$ 和 $12303$ 就是奇怪的数，而 $12345$ 和 $11111$ 则不是。
  小蓝想知道一共有多少个长度为 $n$ 的上述的奇怪的数。你只需要输出答案对 $998244353$ 取模的结果。

【输入格式】

  输入一行包含两个整数 $n,m$，用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

5 5

【样例输出】

6

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$n\le 12$；
  对于 $60\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$5\le n\le 2\times 10^5，0\le m\le 50$。

---

动态规划

---

  因为是要校验连续的 $5$ 个数位上的数字之和是否大于 $m$，自然能设计出状态 $f_{i,a,b,c,d}$，表示第 $i-3$ 个数位上的数字为 $a$；$i-2:b$；$i-1:c$；$i:d$ 的奇怪的数有多少个，容易找到状态转移方程：$$f_{i,a,b,c,d}=\sum f_{i-1,e,a,b,c},a+b+c+d+e\le m.$$  转移复杂度为 $O(n{D}^5)$，其中 $D=5$ 即每个数位可能的取值的个数，这样看来复杂度就超了，$1s$ 指定是跑不出来，于是考虑维护 $f$ 在第二维的前缀和，具体地说我们记：$$g_{i,a,b,c,d}=\sum _{j=0}^a{f}_{i,j,b,c,d}.$$  则状态转移方程可改写为：$$g_{i,a,b,c,d}=g_{i,a-1,b,c,d}+g_{i-1,\max (0,\min (9,m-a-b-c-d)),a,b,c}.$$  转移复杂度为 $O(n{D}^4)$，$1s$ 有那么一点极限，标程很有可能不是动规。还有就是在实现时为了使 $D=5$，转移过程会有一定的微调，具体看代码吧。

#include <stdio.h>

const int M = 12, mod = 998244353;

int n, m, ans, g[2][M][M][M][M];

int main() {
    scanf("%d %d", &n, &m);
    int p = 1, q = 0;
    for (int a = p; a < 10; a += 2)
        for (int b = q; b < 10; b += 2)
            for (int c = p; c < 10; c += 2)
                for (int d = q; d < 10; d += 2) {
                    g[0][a + 2][b][c][d] = g[0][a][b][c][d] + (a + b + c + d <= m);
                }
    for (int i = 5; i <= n; ++i) {
        p ^= 1, q ^= 1;
        for (int a = p; a < 10; a += 2)
            for (int b = q; b < 10; b += 2)
                for (int c = p; c < 10; c += 2)
                    for (int d = q; d < 10; d += 2) {
                        int f = m - a - b - c - d;
                        if (q != (f & 1)) --f;
                        if (f > 8 + p) f = 8 + q;
                        g[i & 1][a + 2][b][c][d] = (g[i & 1][a][b][c][d] + (f < q ? 0 : g[~i & 1][f + 2][a][b][c])) % mod;
                    }
    }
    for (int b = q; b < 10; b += 2)
        for (int c = p; c < 10; c += 2)
            for (int d = q; d < 10; d += 2) {
                int f = m - b - c - d;
                if (f < p) continue;
                if (p != (f & 1)) --f;
                if (f > 8 + p) f = 8 + p;
                ans = (ans + g[n & 1][f + 2][b][c][d]) % mod;
            }
    printf("%d", ans);
}

  输入200000 50，$4000$ 系 $\mathrm{Ryzen}$ 刚好在 $1s$ 跑完，这放在评测机上不开 $\mathrm{O}$$2$ 就超时了。推了半天式子也没什么结果，不过有一种实在的优化方案是：
  记一个长度为 $4$ 奇偶交替数 $n$ 为 $abcd$，它的数位之和为 $s=a+b+c+d$，我们记 $n$ 的逆 $n^{\prime }=(9-a)(9-b)(9-c)(9-d)$ ，则逆的数位之和为 $s^{\prime }=36-s$，显然 $n$ 的全集的按数位之和划分，它的大小以 $18$ 为中点对称。如果输入的 $m$ 在对称点以左，我们按原问题求解，在对称点及对称点以右我们求其逆问题，即一个数 $S$，为长度为 $n$ 且存在连续 $5$ 个数位之和大于 $m$ 的数的个数，此时答案为 $5^n-S$，这样下来状态转移的次数减少一半，可以在时间限制内计算出答案。
  不过相应的代码量翻倍，没这个必要，还是题太臭了。