题解：P11571 「chaynOI R1 T4」橙红色的鱼

ChatSheep · 2025-01-13 13:54:12 · 题解

前言

我的同学说遇见了一道数位动态规划题目，一看是唐题，大约 20 秒就口胡了，20 分钟就差不多写完了（可惜前两小时在上课）。

感觉没什么新鲜感，绿也不是不行。

题解

如果您并没有数位动态规划的基础，请移步我的笔记并且查看本题解对应的关键字内容。

这道题首先就能考虑数位动态规划，从高位向低位的顺序进行关于 x,y 的各个位数（以下记 x',y' 分别为 x,y 的第 i 位）的动态规划。

数据范围的量级就很明确地说明了时间复杂度大概是 O(nms) 的。

这样对于前两个条件是可以很好地维护的，具体来说如下：

• 第一个条件直接边动态规划边维护偏序关系即可，毕竟 x,y,r 的第 i 位都是知道的，前两个是在转移的时候枚举出来的，最后一个是输入告诉我们的。
• 第二个条件直接看转移中枚举的 x \oplus y 即可。

第三个条件只需要在状态中加一个进位标记即可，具体来说，定义状态 jw 表示是否强制钦定第 i 位进位。

然后就可以开始小力分讨：

• 如果这个标记是有的（强制要求进位），那么有两种关于进位的转移：
  • 强制钦定下一位进位，这时就要求 x+y+1 \ge 2 即可，然后加法对应的位置就是 x\oplus y\oplus 1。
  • 强制钦定下一位没有进位，这时就要求 x+y \ge 2 即可，然后加法对应的位置就是 x\oplus y。
• 如果这个标记是没有的（强制要求不进位），那么有两种关于进位的转移：
  • 强制钦定下一位进位，这时就要求 x+y+1 \le 1 即可，然后加法对应的位置就是 x\oplus y\oplus 1。
  • 强制钦定下一位没有进位，这时就要求 x+y \le 1 即可，然后加法对应的位置就是 x\oplus y。

对于标记的转移，这并不是重点，若有需要，请您参考学习笔记的专栏或代码。

于是按照上述说法进行模拟即可，时间复杂度 O(nms)，常数约 2^5。

细节

由于加法会导致进位，进位会导致位数增长，所以考虑直接在数字加一位 0，这样都避免了更多情况的分讨。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

char ss[256];
int n, m, s;
signed  dp[205][205][205][2][2][2];
int dfs(int i, int m, int s, int xy, int yr, int jw) {
    if (m < 0 || s < 0) return 0;
    if (i == n + 1) return jw == 0 && m == 0 && s == 0;
    if (dp[i][m][s][xy][yr][jw] != -1) return dp[i][m][s][xy][yr][jw];
    int ans = 0;
    for (int y = 0; y <= max(yr, (int)(ss[i] - '0')); ++y) {
        for (int x = 0; x <= max(xy, y); ++x) {
            if (jw) { // 强制要求没有本位必须进位
                // 假定下一位没有进位
                if (x + y >= 2) ans += dfs(i + 1, m - (x ^ y), s - (x ^ y), xy || (x != y), yr || (y != (int)(ss[i] - '0')), 0);
                // 假定下一位有进位
                if (x + y + 1 >= 2) ans += dfs(i + 1, m - (x ^ y), s - (x ^ y ^ 1), xy || (x != y), yr || (y != (int)(ss[i] - '0')), 1);
            } else { // 要求不能有进位 
                // 假定下一位没有进位
                if (x + y <= 1) ans += dfs(i + 1, m - (x ^ y), s - (x ^ y), xy || (x != y), yr || (y != (int)(ss[i] - '0')), 0);
                // 假定下一位有进位
                if (x + y + 1 <= 1) ans += dfs(i + 1, m - (x ^ y), s - (x ^ y ^ 1), xy || (x != y), yr || (y != (int)(ss[i] - '0')), 1);
            }
        }
    }
    return dp[i][m][s][xy][yr][jw] = ans % 998244353;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> (ss + 2) >> m >> s;
    ss[1] = '0';
    n = strlen(ss + 1);
    memset(dp, 255, sizeof(dp));
    cout << dfs(1, m, s, 0, 0, 0) << "\n";
    return 0;
}