2025多校冲刺CSP模拟赛7 题目分析

T1

题目概述

求：

\[\sum_{i=1}^n\sum_{j=i}^n[\gcd(i,j)=i\text{ xor } j] \]

其中 \(n\leq 10^7\)。

分析

赛时没有做出来（doge）。

其实细想一下还是可以做的。

不难想到枚举 \(d=\gcd(i,j)\)，那么 \(i\text{ xor }j=d\)。

我们不考虑别的，直接枚举 \(d\mid i\)。

那么得到：\(j=d\text{ xor }i\)（赛时没想到这个）。

然后判断是否相等即可，这样的时间复杂度为 \(\mathcal{O}(n\log^2 n)\)。

显然 \(i\ne j\)，那么我们考虑利用更相减损术变化为 \(\gcd(i,i-j)\)（设 \(i>j\)，下同）。

我们考虑每一位的情况，那么是不是 \(i,j\) 二进制的最高位必须相同啊，如果不相同，那么我们的 \(d\) 在这一位就是 \(1\)，显然此时 \(d>j\)，那么就矛盾了。

于是最高位必须相同，我们考虑后面的位，找出第一个不同的位置，此时一定 \(i\) 这一位为 \(1\)，然后 \(j\) 这一位为 \(0\)，他们相减得到这一位为 \(1\)，此时 \(d\) 这一位也为 \(1\)。

你是不是觉得如果继续这样下去就有 \(i\text{ xor }j=i-j\) 了，但其实可能存在一个或者几个位置使得 \(j\) 的这一位比 \(i\) 大，那么他就要借位，这就会存在一种情况导致 \(i\text{ xor }j>i-j\) 了。

所以说：

\[i-j\leq i\text{ xor }j \]

而 \(d=\gcd(i,i-j)\leq i-j\)。

也就是说我们有：

\[\gcd(i,j)\leq i-j\leq i\text{ xor }j \]

因此两者相等当且仅当：\(\gcd(i,j)=i-j=i\text{ xor } j\)。

枚举 \(d=\gcd(i,j),i\) 然后得到 \(j\) 判断即可。

代码

时间复杂度 \(\mathcal{O}(n\log n)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
// #define N 
using namespace std;
int gcd(int a,int b) {return b ? gcd(b, a % b) : a;
}
int n;
signed main(){// freopen("gcdxor.in","r",stdin),freopen("gcdxor.out","w",stdout);cin >> n;int ans = 0;for (int d = 1;d <= n;d ++)for (int j = d * 2;j <= n;j += d)if ((j ^ d) == j - d) ans ++;cout << ans;return 0;
}

T2

题目概述

现在给你一颗只有一个节点的树，其权值给出，然后处理以下操作：

• 操作一，输入 1 x，在这颗树上面的所有叶子节点扩展出两个节点：设这个节点的权值为 \(w\)，那么扩展出 \(w\) 节点和 \(w\text{ xor } x\) 节点作为它的儿子。
• 操作二，输入 2 x，在这棵树上面，有多少颗子树的异或和为 \(x\)。

其中：\(q\leq 8000,w\leq 2^{13}\)。

分析

byd，赛时看错题目了，直接没做。

其实就是一道诈骗题目。

注意到他生成的其实是一颗完全二叉树。

我们来模拟着一个过程（考虑子树异或和的变化），可以理解成下面这个图：
一开始：

画的不是很好（doge）ww          w^x

当前以 \(w\) 为根的子树异或和为 \(w\text{ xor }x\)。

现在加入 \(y\)。

                  ww          w^xw   w^y   w^x   w^x^y

那么以 \(w\) 为根的子树异或和还是 \(w\text{ xor } x\)。

其实不难证明：对于目前子树大小 \(sz>1\) 的，之后就不会变了，你考虑每次增加的点都直接两两抵消了。

因此我们分两个数组（桶）来记录叶子节点和非叶子节点异或和的值的个树就行了。

诈骗题，骗我 \(100pts\)。

代码

时间复杂度 \(\mathcal{O}(qV)\)。

// ubsan: undefined
// accoders
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
#define N (1 << 13) + 5
const int mod = 998244353;
int k0, Q, cnt[N], res[N], sum[N];
signed main() {freopen("xortree.in", "r", stdin), freopen("xortree.out", "w", stdout);scanf("%lld%lld", &k0, &Q);cnt[k0]++;int tmp, x;while (Q--) {scanf("%lld%lld", &tmp, &x);if (tmp == 1) {for (int i = 0; i < (1 << 13); i++) {res[i] = (res[i] + cnt[i]) % mod;res[i ^ x] = (res[i ^ x] + cnt
}[i]) % mod;sum[i ^ x] = (sum[i ^ x] + cnt[i]) % mod;}for (int i = 0; i < (1 << 13); i++) cnt[i] = res[i], res[i] = 0;} elseprintf("%lld\n", (cnt[x] + sum[x]) % mod);}return 0;

T3

题目概述

给你一个含有 \(n\) 个点的 DAG（有向无环图），每个点有一个权值 \(a_i\)，求每个点的可达点的集合两两与运算的最大值（含自己）。

其中 \(n\leq 5\times 10^5,a_i< 2^60\)。

分析

好题！

赛场应该能切掉的，结果被卡常了只有 \(80pts\)（byd发现了是我没有剪枝优化）。

考虑到 DAG 没有什么性质，只能直接找到可达点，这启示我们将候选的答案合并上去（注意去重）。

一开始想到了 trie树合并，但似乎并没有什么前途，主要是时间上卡不过去。

注意到我们求的答案相当于：

从 \(n\) 个数当中取出两个数进行与运算的最大值。

感觉这个应该候选答案可以优化，所以说，我们大胆猜测能优化到 \(\mathcal{O}(\log a_i)\) 个。

这个其实不难证明，因为你假设答案是 \(M\)，那么其中小于 \(M\) 的肯定不要啊（我就是这里没有删掉导致直接挂到了 \(80pts\)，痛失本场比赛 \(T_3\) 的首杀），那么 \(>M\) 的因为要与答案是 \(M\) 不矛盾所以最多是有 \(\log a_i\) 个的（考虑每一位需要满足的条件）。

然后这道题目就做完了，暴力合并上去即可。

代码

时间复杂度 \(\mathcal{O}(nlog^2 a_i)\)。

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <bits/extc++.h>
#define ll long long
#define N 500005
#define isdigit(ch) ('0' <= ch && ch <= '9')
using namespace std;
using namespace __gnu_pbds;
template<typename T>
void read(T&x) {x = 0;char ch = getchar();for (;!isdigit(ch);ch = getchar());for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
}
template<typename T>
void write(T x) {//no signedif (x > 9) write(x / 10);putchar(x % 10 + '0');
}
struct node{long long val;int id;
};
// inline ll max(ll a,ll b) {
//     return a > b ? a : b;
// }
int n, m;
ll a[N],ans[N];
vector<int> g2[N];
int du[N];
vector<node> cand[N];
bool cmp(const node &a, const node &b) {return a.val > b.val;
}
vector<node> merge(int A,int B,ll &ansVal) {vector<node> res;unordered_map<int, node> best;for (auto &i : cand[A])if (!best.count(i.id))best[i.id] = i;for (auto &i : cand[B])if (!best.count(i.id))best[i.id] = i;for (auto &p : best) res.push_back(p.second);stable_sort(res.begin(),res.end(),cmp);const int K = 64;if ((int)res.size() > K) res.resize(K);//赛时只是钦定了最多M个元素for (int i = 0;i < res.size();i ++)for (int j = i + 1;j < res.size();j ++)ansVal = max(ansVal,res[i].val & res[j].val);while(!res.empty() && res.back().val < ansVal) res.pop_back();//赛时没有打这一行return res;
}
signed main(){// freopen("stone.in","r",stdin),freopen("stone.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1;i <= n;i ++) {cin >> a[i];cand[i].push_back({a[i], i});ans[i] = -1;}for (int i = 1;i <= m;i ++) {int u, v;cin >> u >> v;du[u] ++;g2[v].push_back(u);}queue<int> q;for (int i = 1;i <= n;i ++)if (!du[i]) q.push(i);while (!q.empty()) {int t = q.front();q.pop();for (auto u : g2[t]) {cand[u] = merge(u,t,ans[u]);du[u]--; if (du[u] == 0) q.push(u);}}for (int i = 1;i <= n;i ++) if (ans[i] == -1) printf("-1 ");else write(ans[i]),putchar(' ');return 0;
}

T4