2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑）

题目大意

题目描述
给定三个整数 $a, b, c$，每次可以选择执行以下两种操作之一：

1. $a \leftarrow a + b$

2. $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 中通过题目总结（把题目对取模的要求用注释写在末尾）

收到这场比赛的题目 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 的值，就唯一确定了这个状态。因为起点确定了，增长的值也确定了，那就什么都确定了。（这个是因为异或具有不可重复操作性，操作偶数次等于不操作，操作奇数次等于操作一次）

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/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

源代码（又重新写了一个这个严格的记忆化 bfs）

/**
 * 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……）