2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑） · znzryb
## 题目大意
**题目描述**
给定三个整数 $a, b, c$，每次可以选择执行以下两种操作之一：
1. $a \leftarrow a + b$
1. $a \leftarrow a \oplus b$（$\oplus$ 为按位异或运算）
你可以执行任意次上述操作。请判断最终是否能将 $a$ 变为 $c$。
**输入格式**
第一行为测试数据组数 $T$（$1 \le T \le 10^3$）。
接下来 $T$ 行，每组数据包含三个整数 $a, b, c$（$0 \le a, c \le 10^{18}$，$1 \le b \le 1000$）。
保证在一个测试点内 $\sum b^2 \le 10^6$。
**输出格式**
对于每组数据，如果最终能将 $a$ 变为 $c$，输出 `YES`，否则输出 `NO`。
**样例数据**
```
输入:
5
1 6 7
7 5 13
8 3 16
7 6 17
2 7 8
输出:
YES
NO
YES
YES
NO
```
**样例解释**
- **第一组数据** **`1 6 7`**：初始 $a=1$，执行一次加法操作 $1 + 6 = 7$，即可得到 $c=7$，输出 `YES`。
- **第二组数据** **`7 5 13`**：无法通过进行 $+5$ 或 $\oplus 5$ 操作从 $7$ 得到 $13$，输出 `NO`。
- **第三组数据** **`8 3 16`**：初始 $a=8$，执行路线可为：
$8 \xrightarrow{\oplus 3} 11 \xrightarrow{+3} 14 \xrightarrow{\oplus 3} 13 \xrightarrow{+3} 16$，最终得到 $c=16$，输出 `YES`。
- **第四组数据** **`7 6 17`**：初始 $a=7$，执行路线可为：
$7 \xrightarrow{+6} 13 \xrightarrow{\oplus 6} 11 \xrightarrow{+6} 17$，最终得到 $c=17$，输出 `YES`。
- **第五组数据** **`2 7 8`**：无法通过操作从 $2$ 得到 $8$，输出 `NO`。
## 思路讲解
[2025 ICPC Asia Manila Regional（2025 ICPC 马尼拉）——vp 中通过题目总结（把题目对取模的要求用注释写在末尾）](/2026/03/04/20260304-e4d03354)
收到这场比赛的题目 E. Long Distance Examination（远程操作克隆机器人，两人在不同迷宫中，B 尽力复刻 A 的所有操作）的启发，我们决定重新把这道题目给再盘一盘。
其实说白了，这道题目也很简单，虽然说数字可能很大，但是，我们可以只关注在 $\equiv\pmod b$ 的值，我们以这个为状态，进行记忆化 bfs，自然是非常少的（状态数）。
**记忆化 bfs 最重要的就是确定状态****。**
当然，光有一个目前 mod b 的值是不够的，我们还需要再确定一个状态。
注意到，mod b 的值，是和这个 +b 相关的一个状态，这个提示我们，要采用一个和异或 b 相关的这个值，作为这个状态的组成部分。
**注意到，****异或 b 只能改变后 __lg(b)+1 位****。**
因此，**最后 __lg(b)+1 位，确定了异或 b 操作能够增长（或减小的值）**。再加上 mod b 的值，就唯一确定了这个状态。因为**起点确定了，增长的值也确定了**，那就什么都确定了。（这个是因为异或具有不可重复操作性，操作偶数次等于不操作，操作奇数次等于操作一次）
```cpp
struct ModB_Low_bit {
ll mod_b,low_bit,origin;
bool operator<(const ModB_Low_bit &o) const {
if (o.mod_b!=mod_b) return mod_b<o.mod_b;
return low_bit<o.low_bit;
}
};
```
## AC代码
AC
[https://qoj.ac/submission/1787588](https://qoj.ac/submission/1787588)
::: 源代码
```cpp
// https://qoj.ac/contest/2643/problem/15307
// https://qoj.ac/contest/2643
// by Gospel_rock
// title: ${PROBLEM_NAME}
// GROUP_NAME: ${PROBLEM_GROUP_NAME}
// ONLINE_JUDGE_NAME: ${ONLINE_JUDGE_NAME}
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\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 LD=long double;
// using i128 = __int128;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll lT;
struct Con {
ll val;
int needXor;
};
void Solve(){
ll A,B,C;
cin>>A>>B>>C;
queue<Con> q;
if (A==C) {
cout<<"YES\n";
return;
}
q.push({A,true});
auto check=[&](ll x) {
if (x<=C) {
if ((C-x)%B==0) {
return true;
}
}
return false;
};
unordered_set<ll> vis;
ll timer=0;
while (!q.empty()) {
auto [val,needXor]=q.front();
++timer;
if (timer>B*B+1000) {
break;
}
q.pop();
if (needXor==false) {
if (check(val+B)) {
cout<<"YES\n";
return;
}
if (vis.contains(val+B)) {
continue;
}
vis.insert(val+B);
q.push({val+B,true});
}else {
if (check(val+B)) {
cout<<"YES\n";
return;
}
if (vis.contains(val+B)) {
}else {
vis.insert(val+B);
q.push({val+B,true});
}
if (check(val^B)) {
cout<<"YES\n";
return;
}
if (vis.contains(val^B)) {
continue;
}
vis.insert(val^B);
q.push({(val^B),false});
}
}
cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
Solve();
return 0;
}
/*
1
1 6 7
1
7 5 13
AC
https://qoj.ac/submission/1787521
*/
```
:::
AC
[https://qoj.ac/submission/2095935](https://qoj.ac/submission/2095935)
::: 源代码（又重新写了一个这个严格的记忆化 bfs）
```cpp
/**
* Problem: Plus Xor
* Contest: QOJ
* Judge: Virtual Judge
* URL: https://vjudge.net/problem/QOJ-15307
* Created: 2026-03-05 13:03:25
* 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;
/*
*
*/
struct ModB_Low_bit {
ll mod_b,low_bit,origin;
bool operator<(const ModB_Low_bit &o) const {
if (o.mod_b!=mod_b) return mod_b<o.mod_b;
return low_bit<o.low_bit;
}
};
void Solve() {
ll A,B,C;
cin >> A >> B >> C;
do {
queue<ModB_Low_bit> q;
const ll mask=(1<<(__lg(B)+1))-1;
ll cmodb=C%B;
if (A%B==cmodb && A<=C) {
cout<<"YES\n";
return;
}
q.push({A%B,mask&A,A});
set<ModB_Low_bit> memo={{A%B,mask&A,A}};
while (!q.empty()) {
ModB_Low_bit t=q.front();
q.pop();
for (int i=1;i<=2;++i) {
if (i==1) {
ModB_Low_bit to=t;
to.origin^=B;
to.mod_b=to.origin%B;
to.low_bit=mask&to.origin;
if (to.origin>C && (to.origin^B)>C) {
continue;
}
if (memo.contains(to)) {
continue;
}
if (to.mod_b==cmodb && to.origin<=C) {
cout<<"YES\n";
return;
}
q.push(to);
memo.insert(to);
}else if (i==2) {
ModB_Low_bit to=t;
to.origin+=B;
to.mod_b=to.origin%B;
to.low_bit=mask&to.origin;
if (to.origin>C && (to.origin^B)>C) {
continue;
}
if (memo.contains(to)) {
continue;
}
if (to.mod_b==cmodb && to.origin<=C) {
cout<<"YES\n";
return;
}
q.push(to);
memo.insert(to);
}
}
}
cout<<"NO\n";
return;
}while (false);
}
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://qoj.ac/submission/2095935
*/
```
:::
## 心路历程（WA，TLE，MLE……）
