Znzryb's Blog
0%

2026 杭电春季联赛 3——1005-月球异或

Posted on Edited on

题目大意

题目大意

定义一种自然数下的二元运算「月球异或」（记作 ⊛\circledast）：将两个自然数转换为三进制后，对每一位分别相加并对 33 取模（即三进制下的不进位加法）。例如 8(10)⊛16(10)=022(3)⊛121(3)=110(3)=12(10)8_{(10)} \circledast 16_{(10)} = 022_{(3)} \circledast 121_{(3)} = 110_{(3)} = 12_{(10)}。

现给定一个长度为 NN 的自然数序列 v1,v2,…,vNv_1, v_2, \dots, v_N。你可以对序列中的任意元素 viv_i 执行以下两种操作任意次（包含零次）：

  1. vi←vi⊛viv_i \leftarrow v_i \circledast v_i

  2. vi←0v_i \leftarrow 0

有 QQ 次独立的询问，每次询问给出一个自然数 ss。对于每次询问，你需要判断能否通过若干次上述操作，使得序列全部元素的「月球异或」和等于 ss（即 v1⊛v2⊛⋯⊛vN=sv_1 \circledast v_2 \circledast \dots \circledast v_N = s）。

数据范围

测试组数：1≤T≤1000001 \le T \le 100000
序列长度与询问次数：1≤N,Q≤1061 \le N, Q \le 10^6，且所有测试组的 ∑N,∑Q≤2×106\sum N, \sum Q \le 2 \times 10^6
序列元素与询问值：0≤vi,si≤10180 \le v_i, s_i \le 10^{18}

样例数据

输入：

1
2
3
4
5
6
7
8
9
10
3
1 4
1
0 1 2 3
3 5
0 5 10
4 5 6 7 8
3 6
8 16 32
12 17 57 41 4 44

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Yes
Yes
Yes
No
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes

样例解释

以第一组样例为例：
此时 N=1,Q=4N=1, Q=4，序列只包含一个元素 v1=1v_1 = 1。
四次询问的值分别为 s=0,1,2,3s = 0, 1, 2, 3。

对于 v1=1v_1 = 1（三进制表示为 01(3)01_{(3)}），它可能变化得到的状态有：

  • 执行零次操作：得到原来的值 11。

  • 执行一次第一种操作：1⊛1=1(3)+1(3)(mod3)=2(3)=21 \circledast 1 = 1_{(3)} + 1_{(3)} \pmod 3 = 2_{(3)} = 2。

  • 执行一次第二种操作：直接变为 00。

因为操作本质上是对三进制的每一位独立进行乘法并对 33 取模，或者直接置零，所以原本为 00 的高位（如 313^1 对应的位）永远不可能变成非 00 值。
目标 s=3s=3 在三进制下表示为 10(3)10_{(3)}，其第 11 位（对应数值 33）的值为 11，而 v1v_1 无论怎么操作在第 11 位上永远是 00，因此永远无法得到 33。
最终对于 0,1,2,30, 1, 2, 3 的询问，前三个可以得到，后一个无法得到，分别输出 Yes、Yes、Yes、No。

思路讲解

其实，不难发现，我们其实就是要看一个数字能不能用我们的这个三进制异或线性基表示出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137


// 模 p 意义下的线性基（用于处理 p 进制下的无进位加法，本题中 p = 3）
class modn_XOR_base {  
private:  
    vector<ll> base;                // 记录主元位置对应的原始数值
    vector<vector<ll>> mat;         // mat[i] 存储最高位为 i 且系数已被标准化为 1 的基向量
    ll mod;                         // 模数 p（要求 p 为质数，才能使用费马小定理求逆元）


    // 快速幂计算 (a^b % mod)
    ll power(ll a, ll b) const {
        ll res = 1;
        a %= mod;
        while (b > 0) {
            if (b & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }

    // 费马小定理求逆元（因为 mod 为质数）
    ll modInverse(ll n) const {
        return power(n, mod - 2);
    }

public:  
    // 构造函数，初始化模数和基数组的大小
    // 64 位数组足以容纳 10^18 在三进制下的最大位数（约为 38 位）
    modn_XOR_base(ll Mod) {  
        mod = Mod; 
        base.assign(64, 0);                      
        mat.assign(64, vector<ll>(64, 0));       
    }  

    // 插入元素 x 到线性基中
    // 如果 x 能被已有的线性基表出，返回 false；否则将其作为新的基插入并返回 true
    bool insert(ll x) {
        ll orig_x = x;
        vector<ll> v(64, 0);
        
        // 将 x 转换为 mod 进制的向量表示（从低位到高位分离）
        for (int i = 0; i < 64; ++i) {
            v[i] = x % mod;
            x /= mod;
        }

        // 从高位到低位进行高斯消元操作
        for (int i = 63; i >= 0; --i) {
            if (v[i] == 0) continue; // 当前位为 0，无需处理

            // 如果当前位没有主元（即线性基在此位为空）
            if (base[i] == 0) {
                ll inv = modInverse(v[i]); // 求当前位系数的逆元
                // 将整个向量乘以逆元，使得最高位（第 i 位）的系数标准化为 1
                for (int j = 0; j <= i; ++j) {
                    mat[i][j] = (v[j] * inv) % mod;
                }
                base[i] = orig_x; // 记录在该位有主元被插入
                return true;      // 成功插入新的基向量，向量空间维数 +1
            }

            // 如果当前位已经有主元了，利用已有的基向量 mat[i] 消去当前位 v[i]
            ll k = v[i]; // 因为 mat[i][i] 已经被标准化为 1，所以要消去 v[i]，需减去 mat[i] 的 k 倍
            for (int j = 0; j <= i; ++j) {
                v[j] = (v[j] - k * mat[i][j]) % mod;
                if (v[j] < 0) v[j] += mod; // 保证结果始终在 [0, mod-1] 的合法范围内
            }
        }
        // 如果循环结束，说明整个向量被彻底消成了 0，即它可以由已有基表出
        return false; 
    }  

    
    // 查询元素 x 能否被当前的线性基表出
    bool query(ll x) const {
        vector<ll> v(64, 0);
        
        // 同样将待查询的 x 转换为 mod 进制的向量表示
        for (int i = 0; i < 64; ++i) {
            v[i] = x % mod;
            x /= mod;
        }

        // 从高位到低位依次尝试被线性基消元
        for (int i = 63; i >= 0; --i) {
            if (v[i] == 0) continue;
            
            // 如果 x 在某一位不为 0，但线性基该位为空，说明无法被表出，直接返回 false
            if (base[i] == 0) return false;

            // 利用线性基消去当前位
            ll k = v[i];
            for (int j = 0; j <= i; ++j) {
                v[j] = (v[j] - k * mat[i][j]) % mod;
                if (v[j] < 0) v[j] += mod;
            }
        }
        
        // 如果所有非零位都被成功消去（最终变为全 0 向量），说明 x 能被完美表出
        return true;
    }  
};

int main() {
    
    // 优化标准 I/O 速度，避免因为读写大规模数据超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    

    int T;
    cin >> T;
    while (T--) {
        // 针对题目“月球异或”：三进制下的每一位独立相加后模 3，因此实例化模数为 3 的线性基
        modn_XOR_base base(3);
        ll N, Q;
        cin >> N >> Q;
        
        // 读入序列 v 并将每一个元素构建到线性基中
        // 注意：线性基可以允许重复操作操作对象 v_i <- v_i ⊛ v_i，本质就是该向量的数乘操作
        for(int i = 0; i < N; ++i){
            ll x;
            cin >> x;
            base.insert(x);
        }
        
        // 读入每个询问的数值 t，利用已求得的线性基判断是否能生成 t
        for(int i = 0; i < Q; ++i){
            ll t;
            cin >> t;
            cout << (base.query(t) ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

AC代码

AC

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=7820&from=rank

心路历程（WA，TLE，MLE……）