由于异或运算按位独立，我们可以用一个经典的trick：拆位 计算该位上的贡献，再把每一位的贡献加起来，得到答案。
对于第 i 位（i = 0 ~ 30），我们只关心每个顶点的这一位是 0 还是 1。
-
用
a[j] = (v[j] >> i) & 1取出顶点j的第i位值（0 或 1）。 -
因为图是无向的，且路径长度固定为 2，我们可以枚举每一个中间顶点
v，然后去看它的邻居u和w。
对固定的中间顶点 v：
设它的邻居集合中：
cnt0= 邻居中第i位为 0 的个数cnt1= 邻居中第i位为 1 的个数
情况 1：a[v] == 0（中间顶点第 i 位为 0）
要使三个顶点有奇数个 1，则邻居中必须有恰好一个 1
- 一个邻居为 1，另一个为 0 → 无序对数量 =
cnt0 * cnt1。
情况 2：a[v] == 1（中间顶点第 i 位为 1）
要使奇数个 1，则邻居中必须有 2 个 0 或者 2 个 1。
- 两个邻居都是 0：方案数 =
cnt0 * (cnt0 - 1) / 2 - 两个邻居都是 1：方案数 =
cnt1 * (cnt1 - 1) / 2 - 总方案数 = 两者相加。
接着
- 设第
i位上得到的合法路径总数为cnt。 - 这一位对最终答案的贡献 =
cnt * 2^i。 - 记得取模
时间复杂度
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 100;
const double EPS = 1e-8;
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll n, m;
cin >> n >> m;
vector<ll> v(n + 1);
for (ll i = 1; i <= n; i++)
cin >> v[i];
// 邻接表建图
vector g(n + 1, vector<ll>());
for (ll i = 1; i <= m; i++)
{
ll x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
ll ans = 0; // 最终答案
// 枚举每一位（0 ~ 30，因为 a_i ≤ 1e9 < 2^30）
for (ll i = 0; i <= 30; i++)
{
// a[j] 存储第 j 个顶点在当前位上的值（0 或 1）
vector<ll> a(n + 1);
for (ll j = 1; j <= n; j++)
a[j] = (v[j] >> i) & 1;
ll cnt = 0; // 当前位上异或结果为 1 的路径总数
// 枚举每个顶点作为中间顶点 v
for (ll j = 1; j <= n; j++)
{
ll cnt0 = 0, cnt1 = 0; // 统计其邻居中当前位为 0 和 1 的个数
for (auto e : g[j])
{
if (a[e] == 0)
cnt0++;
else
cnt1++;
}
// 根据中心顶点的当前位值，计算合法邻居对的数量
if (a[j] == 0)
cnt += cnt0 * cnt1; // 中心为 0 时，需要邻居一个0和一个1
else
cnt += cnt0 * (cnt0 - 1) / 2 + cnt1 * (cnt1 - 1) / 2; // 中心为 1 时，需要邻居两个0或两个1
}
cnt %= MOD; // 取模防止溢出
ans = (ans + cnt * (1ll << i) % MOD) % MOD; // 贡献 = 路径数 * (1 << i)，累加到答案
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
//cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号