线性基——2026杭电春季联赛第三场1005月球异或

前言本人蒟蒻如有错误还请指出。前不久刚学了线性基结果就用上了。线性基yyds没学过线性基的出门左拐放一个之前写的线性基笔记原题链接题目大意新定义三进制下的异或运算。再给你一个长度为的数组你可以选择一个序号使或者。然后有次询问每次问是否可以通过若干次操作使得。思路显然这题与原线性基模板题的区别只在于把二进制改为了三进制那么我们就先来考虑这个三进制是如何异或的根据题目所给的公式可知两个数异或时每一位最后的结果应为这两个数在三进制下这一位数之和取模于3。如果令的第位为的第位为那么第位的异或结果为以下面为例只需简单模拟一遍即可void init()//预处理3的幂次 { fact[0] 1; for (int i 1; i 40; i) fact[i] fact[i - 1] * 3; } int cal(int x, int y) // 计算三进制下x^y的结果 { int res 0, p 0; while (x || y) { res (x y) % 3 * fact[p]; x / 3; y / 3; p; } return res; }接下来考虑怎么构造线性基构造方法与原构造方法相同唯一的区别就是二进制改为了三进制。在二进制下每一位只有两种可能而在三进制下每一位有三种可能。由于因此当我们遇到三进制下这一位为 2 时我们只需要将他异或上他自己这样这一位就位变为 1 这样以来就和二进制一样了。当我们需要把 1 异或成 0 时我们需要异或上三次 1 即。int find(int x, int p) // 求x在三进制下第p位的值 { while (p--) x / 3; return x % 3; } bool insert(int val, int idx) { for (int i 39; i 0; i--) { int t find(val, i); if (t) { if (!d[i]) { if (t 2) // 这一位为2时异或他自己使其变为1 val cal(val, val); d[i] val; return true; } if (t 1) // 这一位为1时需要多异或一次1 val cal(val, val); val cal(val, d[i]); } } return false; }查询是否可以得到也是和二进制下线性基的查询一样只需要看能否将其插入到线性基中若不能插入即在中途被异或成0了说明可以被线性基中的一些数异或得到。由于0也是允许的特判即可。bool check(int val) { if (val 0) return true; for (int i 39; i 0; i--) { int t find(val, i); if (t) { if (!d[i]) return false; if (t 1) val cal(val, d[i]); val cal(val, d[i]); } } return true; }这样你就成功写出这道题了代码下面是AC代码#include bits/stdc.h using namespace std; #define int long long #define endl \n typedef pairint, int pii; const int INF 1e18; const int N 1e6 5, mod 998244353; int n, m; int a[N]; int d[61], p[61], fact[61]; void init() // 预处理3的幂次 { fact[0] 1; for (int i 1; i 40; i) fact[i] fact[i - 1] * 3; } int cal(int x, int y) // 计算三进制下x^y的结果 { int res 0, p 0; while (x || y) { res (x y) % 3 * fact[p]; x / 3; y / 3; p; } return res; } int find(int x, int p) // 求x在三进制下第p位的值 { while (p--) x / 3; return x % 3; } bool insert(int val, int idx) { for (int i 39; i 0; i--) { int t find(val, i); if (t) { if (!d[i]) { if (t 2) // 这一位为2时异或他自己使其变为1 val cal(val, val); d[i] val; return true; } if (t 1) // 这一位为1时需要多异或一次1 val cal(val, val); val cal(val, d[i]); } } return false; } bool check(int val) { if (val 0) return true; for (int i 39; i 0; i--) { int t find(val, i); if (t) { if (!d[i]) return false; if (t 1) val cal(val, d[i]); val cal(val, d[i]); } } return true; } void clear() { for (int i 0; i 40; i) d[i] p[i] 0; } void solve() { clear(); cin n m; for (int i 1; i n; i) { int x; cin x; insert(x, i); } while (m--) { int x; cin x; if (check(x)) cout Yes endl; else cout No endl; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); int _ 1; cin _; while (_--) solve(); }