自动搬运

查看原文

来自洛谷，原作者为

	CuteChat **

搬运于2025-08-24 23:08:31，当前版本为作者最后更新于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;
}