2026 杭电春季联赛 2——1001-湖上午后(a | b+ a & b = a + b)(数位 dp 在统计对数的时候不能是用【0,r】-【0,l-1】的这种方法) · znzryb
## 题目大意
**题目描述**
给定两个以二进制字符串形式表示的非负整数 $s$ 和 $t$。
请计算有多少组整数对 $(a, b)$ 满足:
1. 取值范围:$a$ 和 $b$ 均在区间 $[s, t]$ 内。
1. 满足等式:$a \times b = (a \text{ or } b) \times (a \text{ and } b)$
其中 $\text{or}$ 表示按位或运算,$\text{and}$ 表示按位与运算。
最终答案需要对 $998244353$ 取模。
**输入格式**
第一行包含一个整数 $Q$($1 \le Q \le 20$),表示测试用例的数量。
接下来 $Q$ 行,每行包含两个 $01$ 字符串 $S$ 和 $T$,分别表示非负整数 $s$ 和 $t$ 的二进制形式。
数据保证 $s$ 和 $t$ 的二进制形式无前导零,且满足 $s \le t$,$1 \le |S|, |T| \le 5 \times 10^5$。
**输出格式**
对于每个测试用例,输出一行一个非负整数,表示满足条件的解的数量对 $998244353$ 取模后的值。
**样例数据**
**输入**
```
6
11 1000
1000 1001
0 100
11 111
10 111
0 11111
```
**输出**
```
18
4
17
17
24
454
```
**样例解释**
原题未提供具体的样例解释内容,此处按要求对样例数据的完整输入输出进行展示。
## 思路讲解
这道题目的数的规律我们很容易从这个打表看出来。
我们下面只打印了有序对:
```cpp
[-] FAILURE: RUNTIME ERROR
i = [0]
j = [1]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000001]
-----------
i = [0]
j = [2]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000010]
-----------
i = [0]
j = [3]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000011]
-----------
i = [0]
j = [4]
bitset<10>(i) = [0000000000]
bitset<10>(j) = [0000000100]
-----------
i = [1]
j = [3]
bitset<10>(i) = [0000000001]
bitset<10>(j) = [0000000011]
-----------
i = [2]
j = [3]
bitset<10>(i) = [0000000010]
bitset<10>(j) = [0000000011]
-----------
cnt = [6]
```
不难看出,我们所要求的是:

当然,如果你要推出这个东西的话,**你需要知道一个定理**:

对于任意两个非负整数 $a$ 和 $b$,我们设 $x = a \text{ or } b$,$y = a \text{ and } b$。
在位运算中,有一个非常经典的定律,即它们的**和永远保持不变**:
$$
x + y = a + b
$$
**为什么?** 我们可以单独看某一个二进制位:
- 如果 $a$ 和 $b$ 这一位都是 0,那么 $x$ 是 0,$y$ 也是 0。$(0+0 = 0+0)$
- 如果 $a$ 和 $b$ 这一位都是 1,那么 $x$ 是 1,$y$ 也是 1。$(1+1 = 1+1)$
- 如果 $a$ 和 $b$ 这一位是一个 1 一个 0,那么 $x$ (OR) 会拿到这个 1,$y$ (AND) 是 0。$(1+0 = 1+0)$
可以看出,无论哪种情况,进位和本质的值都不会丢失,所以 $a \text{ or } b$ 加上 $a \text{ and } b$ 必定等于 $a + b$。
接着,我们把这两个式子联立,可以得到:

那么不难得到:

不过更难的应该是更进一步的这个求解。
[HDU - 2089- 不要62](/2025/01/14/20250114-6b4320a2)
这道题目和普通的数位 dp 最大的不同的就是,你一定要同时考虑这个低位和高位。

具体而言,为什么相减会出现问题呢?

那么我们上面讲了不能这么做,然后**下面我们来讲讲应该怎么做**。

然后下面是一种比较 shi 的实现方式,因为就是分类讨论。
::: if else 的这个实现方式需要人工判断转移,非常麻烦,而且容易写错
```cpp
void make_s_t_same_len(string &s, const string &t) {
ll lenS = SZ(s), lenT = SZ(t);
s = string(lenT - lenS, '0') + s;
}
auto execute_dp(const string &l, const string &r) {
// 高位对 a 的限制(未来),低位对 b 的限制(未来)
// 所谓还受到限制,就是前缀完全相等
vector<vector<ll> > dp(2, vector<ll>(2));
for (int i = 0; i < SZ(l); ++i) {
ll r_bit = r[i] - '0';
ll l_bit = l[i] - '0';
// 设定初值
if (i == 0) {
if (r_bit && !l_bit) {
// 都填 1 1,之后这个低位就没有限制,随便填了
dp[0][1] = 1;
// 都填 1 0
dp[0][0] = 1;
// 填入 0,0,未来 a 的高位就没有限制了
dp[1][0] = 1;
} else if (l_bit && r_bit) {
// 填入 1 1,但是之后还是都有限制
dp[0][0] = 1;
// 填入 1 0 不可能,b 填 0 突破了下界限制
// 填入 0 0 也不可能,b 填 0 突破了下界限制
} else {
dp[0][0] = 1;
// assert(0);
}
continue;
}
vector<vector<ll> > ndp(2, vector<ll>(2));
// r 为 0,没法突破上界限制,l 为 1,没法突破下界限制
if (r_bit == 0 && l_bit == 0) {
// 只能突破下界限制
// 填入 0 0,这样子就是严格相等的
ndp[0][0] = dp[0][0];
// 0? 填 11 会突破上界限制,不能填
ndp[0][1] = dp[0][1] /*+ dp[0][0]*/;
// ?0
ndp[1][0] = dp[1][0] * 2;
// 填00或者10或者11 填11,扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[1][0];
} else if (r_bit == 0 && l_bit == 1) {
// 什么限制都无法突破
ndp[0][0] = 0;
ndp[0][1] = dp[0][1];
ndp[1][0] = dp[1][0];
ndp[1][1] = dp[1][1] * 3;
} else if (r_bit == 1 && l_bit == 1) {
// 可以突破上界限制
ndp[0][0] = dp[0][0];
// 1?
ndp[0][1] = dp[0][1] * 2;
// ?1 填入 0 0不合法,会突破下界限制
ndp[1][0] = dp[1][0] /*+ dp[0][0]*/;
// 填入 0 0,扔掉上界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1];
} else if (r_bit == 1 && l_bit == 0) {
// 什么限制都可以突破
ndp[0][0] = dp[0][0];
// 1? 需要这个填入 11,扔掉下界限制
ndp[0][1] = dp[0][1] * 2 + dp[0][0];
// ?0 需要这个填入 00,扔掉上界限制
ndp[1][0] = dp[1][0] * 2 + dp[0][0];
// 填入 00 扔掉上界限制 填入 11 扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1] + dp[1][0];
}
ndp[0][0] %= mod;
ndp[1][1] %= mod;
ndp[1][0] %= mod;
ndp[0][1] %= mod;
swap(dp, ndp);
}
return dp;
}
ll get_val_from_str(const string &s) {
ll res = 0;
ll pow2 = 1;
for (int i = SZ(s) - 1; i >= 0; --i) {
ll val = s[i] - '0';
res += pow2 * val;
res %= mod;
pow2 *= 2;
pow2 %= mod;
}
return res;
}
ll gen_ans(const auto &dp, ll l, ll r) {
ll ans = (dp[0][0] + dp[1][1] + dp[0][1] + dp[1][0]) % mod;
ans = 2 * ans - (r - l + 1);
ans %= mod;
if (ans < 0) {
ans += mod;
}
return ans;
}
void Solve() {
string s, t;
cin >> s >> t;
make_s_t_same_len(s, t);
auto dp = execute_dp(s, t);
cout << gen_ans(dp, get_val_from_str(s), get_val_from_str(t)) << "\n";
}
```
:::
```cpp
constexpr int moves[][2] = {{0, 0}, {1, 0}, {1, 1}};
auto execute_dp(const string &l, const string &r) {
array<array<ll, 2>, 2> dp = {};
dp[0][0] = 1;
for (int i = 0; i < (int) l.size(); ++i) {
int r_bit = r[i] - '0', l_bit = l[i] - '0';
array<array<ll, 2>, 2> ndp = {};
for (auto &[a_r,b_l]: moves) {
for (int status_r = 0; status_r <= 1; ++status_r) {
for (int status_l = 0; status_l <= 1; ++status_l) {
// 受限制的时候,不可以超过上界
if (status_r == 0 && a_r > r_bit) {
continue;
}
// 受限制的时候,不可以越过下界
if (status_l == 0 && b_l < l_bit) {
continue;
}
// 继承原来的状态
ll to_r = status_r, to_l = status_l;
// 不一样而且合法?那就变为这个 1 状态(即不受限制状态,因为已经偏离了前缀了)
if (a_r != r_bit) {
to_r = 1;
}
if (b_l != l_bit) {
to_l = 1;
}
ndp[to_r][to_l] += dp[status_r][status_l];
ndp[to_r][to_l] %= mod;
}
}
}
swap(dp, ndp);
}
return dp;
// return (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % mod;
}
```
在知道 dp 数组以后,答案像下面这样子求:
```cpp
ll gen_ans(const auto &dp, ll l, ll r) {
ll ans = (dp[0][0] + dp[1][1] + dp[0][1] + dp[1][0]) % mod;
ans = 2 * ans - (r - l + 1);
ans %= mod;
if (ans < 0) {
ans += mod;
}
return ans;
}
```
## AC代码
AC
[https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17914](https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17914)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: 湖上午后
* Contest:
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1001
* Created: 2026-03-27 21:18:07
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
void make_s_t_same_len(string &s, const string &t) {
ll lenS = SZ(s), lenT = SZ(t);
s = string(lenT - lenS, '0') + s;
}
auto execute_dp(const string &l, const string &r) {
// 高位对 a 的限制(未来),低位对 b 的限制(未来)
// 所谓还受到限制,就是前缀完全相等
vector<vector<ll> > dp(2, vector<ll>(2));
for (int i = 0; i < SZ(l); ++i) {
ll r_bit = r[i] - '0';
ll l_bit = l[i] - '0';
// 设定初值
if (i == 0) {
if (r_bit && !l_bit) {
// 都填 1 1,之后这个低位就没有限制,随便填了
dp[0][1] = 1;
// 都填 1 0
dp[0][0] = 1;
// 填入 0,0,未来 a 的高位就没有限制了
dp[1][0] = 1;
} else if (l_bit && r_bit) {
// 填入 1 1,但是之后还是都有限制
dp[0][0] = 1;
// 填入 1 0 不可能,b 填 0 突破了下界限制
// 填入 0 0 也不可能,b 填 0 突破了下界限制
} else {
dp[0][0] = 1;
// assert(0);
}
continue;
}
vector<vector<ll> > ndp(2, vector<ll>(2));
// r 为 0,没法突破上界限制,l 为 1,没法突破下界限制
if (r_bit == 0 && l_bit == 0) {
// 只能突破下界限制
// 填入 0 0,这样子就是严格相等的
ndp[0][0] = dp[0][0];
// 0? 填 11 会突破上界限制,不能填
ndp[0][1] = dp[0][1] /*+ dp[0][0]*/;
// ?0
ndp[1][0] = dp[1][0] * 2;
// 填00或者10或者11 填11,扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[1][0];
} else if (r_bit == 0 && l_bit == 1) {
// 什么限制都无法突破
ndp[0][0] = 0;
ndp[0][1] = dp[0][1];
ndp[1][0] = dp[1][0];
ndp[1][1] = dp[1][1] * 3;
} else if (r_bit == 1 && l_bit == 1) {
// 可以突破上界限制
ndp[0][0] = dp[0][0];
// 1?
ndp[0][1] = dp[0][1] * 2;
// ?1 填入 0 0不合法,会突破下界限制
ndp[1][0] = dp[1][0] /*+ dp[0][0]*/;
// 填入 0 0,扔掉上界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1];
} else if (r_bit == 1 && l_bit == 0) {
// 什么限制都可以突破
ndp[0][0] = dp[0][0];
// 1? 需要这个填入 11,扔掉下界限制
ndp[0][1] = dp[0][1] * 2 + dp[0][0];
// ?0 需要这个填入 00,扔掉上界限制
ndp[1][0] = dp[1][0] * 2 + dp[0][0];
// 填入 00 扔掉上界限制 填入 11 扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1] + dp[1][0];
}
ndp[0][0] %= mod;
ndp[1][1] %= mod;
ndp[1][0] %= mod;
ndp[0][1] %= mod;
swap(dp, ndp);
}
return dp;
}
ll get_val_from_str(const string &s) {
ll res = 0;
ll pow2 = 1;
for (int i = SZ(s) - 1; i >= 0; --i) {
ll val = s[i] - '0';
res += pow2 * val;
res %= mod;
pow2 *= 2;
pow2 %= mod;
}
return res;
}
ll gen_ans(const auto &dp, ll l, ll r) {
ll ans = (dp[0][0] + dp[1][1] + dp[0][1] + dp[1][0]) % mod;
#ifdef LOCAL
debug(l);
debug(r);
debug2d(dp);
debug(ans);
#endif
ans = 2 * ans - (r - l + 1);
ans %= mod;
if (ans < 0) {
ans += mod;
}
return ans;
}
void Solve() {
string s, t;
cin >> s >> t;
make_s_t_same_len(s, t);
auto dp = execute_dp(s, t);
cout << gen_ans(dp, get_val_from_str(s), get_val_from_str(t)) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
*/
```
:::
AC
[https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17962](https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=17962)
::: 采用了更好实现方式的代码
```cpp
// teamname: Gospel_rock
/**
* Problem: 湖上午后
* Contest:
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1001
* Created: 2026-03-27 21:18:07
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
void make_s_t_same_len(string &s, const string &t) {
ll lenS = SZ(s), lenT = SZ(t);
s = string(lenT - lenS, '0') + s;
}
auto execute_dp(const string &l, const string &r) {
// 高位对 a 的限制(未来),低位对 b 的限制(未来)
// 所谓还受到限制,就是前缀完全相等
vector<vector<ll> > dp(2, vector<ll>(2));
for (int i = 0; i < SZ(l); ++i) {
ll r_bit = r[i] - '0';
ll l_bit = l[i] - '0';
// 设定初值
if (i == 0) {
if (r_bit && !l_bit) {
// 都填 1 1,之后这个低位就没有限制,随便填了
dp[0][1] = 1;
// 都填 1 0
dp[0][0] = 1;
// 填入 0,0,未来 a 的高位就没有限制了
dp[1][0] = 1;
} else if (l_bit && r_bit) {
// 填入 1 1,但是之后还是都有限制
dp[0][0] = 1;
// 填入 1 0 不可能,b 填 0 突破了下界限制
// 填入 0 0 也不可能,b 填 0 突破了下界限制
} else {
dp[0][0] = 1;
// assert(0);
}
continue;
}
vector<vector<ll> > ndp(2, vector<ll>(2));
// r 为 0,没法突破上界限制,l 为 1,没法突破下界限制
if (r_bit == 0 && l_bit == 0) {
// 只能突破下界限制
// 填入 0 0,这样子就是严格相等的
ndp[0][0] = dp[0][0];
// 0? 填 11 会突破上界限制,不能填
ndp[0][1] = dp[0][1] /*+ dp[0][0]*/;
// ?0
ndp[1][0] = dp[1][0] * 2;
// 填00或者10或者11 填11,扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[1][0];
} else if (r_bit == 0 && l_bit == 1) {
// 什么限制都无法突破
ndp[0][0] = 0;
ndp[0][1] = dp[0][1];
ndp[1][0] = dp[1][0];
ndp[1][1] = dp[1][1] * 3;
} else if (r_bit == 1 && l_bit == 1) {
// 可以突破上界限制
ndp[0][0] = dp[0][0];
// 1?
ndp[0][1] = dp[0][1] * 2;
// ?1 填入 0 0不合法,会突破下界限制
ndp[1][0] = dp[1][0] /*+ dp[0][0]*/;
// 填入 0 0,扔掉上界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1];
} else if (r_bit == 1 && l_bit == 0) {
// 什么限制都可以突破
ndp[0][0] = dp[0][0];
// 1? 需要这个填入 11,扔掉下界限制
ndp[0][1] = dp[0][1] * 2 + dp[0][0];
// ?0 需要这个填入 00,扔掉上界限制
ndp[1][0] = dp[1][0] * 2 + dp[0][0];
// 填入 00 扔掉上界限制 填入 11 扔掉下界限制
ndp[1][1] = dp[1][1] * 3 + dp[0][1] + dp[1][0];
}
ndp[0][0] %= mod;
ndp[1][1] %= mod;
ndp[1][0] %= mod;
ndp[0][1] %= mod;
swap(dp, ndp);
}
return dp;
}
ll get_val_from_str(const string &s) {
ll res = 0;
ll pow2 = 1;
for (int i = SZ(s) - 1; i >= 0; --i) {
ll val = s[i] - '0';
res += pow2 * val;
res %= mod;
pow2 *= 2;
pow2 %= mod;
}
return res;
}
ll gen_ans(const auto &dp, ll l, ll r) {
ll ans = (dp[0][0] + dp[1][1] + dp[0][1] + dp[1][0]) % mod;
#ifdef LOCAL
debug(l);
debug(r);
debug2d(dp);
debug(ans);
#endif
ans = 2 * ans - (r - l + 1);
ans %= mod;
if (ans < 0) {
ans += mod;
}
return ans;
}
void Solve() {
string s, t;
cin >> s >> t;
make_s_t_same_len(s, t);
auto dp = execute_dp(s, t);
cout << gen_ans(dp, get_val_from_str(s), get_val_from_str(t)) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程(WA,TLE,MLE……)