E 小苯的xor图

这道题要求我们计算一个关于图中所有长度为2的路径的特定权值总和。一个长度为2的路径由三个点 u,v,w 构成，其中边 (u,v) 和 (v,w) 存在。

形式化地说，我们需要计算的公式是：

其中 N(v) 表示节点 v 的邻居集合。u<w 是为了确保每对邻居只被计算一次。

思路：按位贡献

一个数 X 的值可以表示为 sum_b=0^k*2^b

就是cdot(X_b)，其中 X_b 是 X 在二进制表示下的第 b 位。利用加法的分配律，总和 S 就可以转化为计算每一位贡献的总和：

这里的 (a_i)_b 指的是 a_i 的二进制第 b 位。

现在，问题转化为：对于每一个二进制位 b，计算有多少个路径 (u,v,w) 使得其权值的第 b 位为1。

具体代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int M = 200005;
const int MOD = 998244353;

vector<int> j[M];
int n,m,a[M];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        j[u].push_back(v);
        j[v].push_back(u);
    }
    ll t = 0;
    // 按位枚举
    for (int b = 0; b <= 30; ++b) {
        ll cnt = 0; 
        // 枚举中心点v
        for (int v = 1; v <= n; ++v) {
            ll c1 = 0,c2 = 0; 
            // 统计邻居中第b位为0和1的数量
            for (int ne : j[v]) {
                if ((a[ne] >> b) & 1) {
                    c2++;
                } else {
                    c1++;
                }
            }
            ll p = 0;
            // 根据中心点v的第b位计算贡献
            if ((a[v] >> b) & 1) { 
                // (a_v)_b = 1, 需要 (a_u)_b == (a_w)_b
                p = (c1 * (c1 - 1) / 2) + (c2 * (c2 - 1) / 2);
            } else { 
                // (a_v)_b = 0, 需要 (a_u)_b != (a_w)_b
                p = c1 * c2;
            }
            cnt += p;
        }
        // 累加当前位的总贡献
        ll p0 = (1LL << b) % MOD,b0 = (cnt % MOD * p0) % MOD;
        t = (t + b0) % MOD;
    }
    cout << t << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

F 小苯的前缀gcd构造

思路：动态规划+bitset

我们定义 dp[i][g] 为一个 bitset。如果 dp[i][g] 的第 s 位为1，则表示存在一个长度为 i、以 g 结尾、且满足整除条件的序列，其元素总和为 s。

在 bitset 上，这相当于将 dp[i−1][k] 中所有为1的位向左移动 g 位。我们将所有合法的 k（即 g 的倍数）所对应的 dp[i−1][k] 左移 g 位后的结果进行按位或运算，就得到了 dp[i][g]

状态转移方程：

基础情况

当 i=1 时，序列只有一个元素 g。其和就是 g。所以，对于所有 g in[1,m]，我们在 dp[1][g] 的第 g 位上置1。

具体解法

1. 完成DP表格的计算后，我们检查是否存在解。我们遍历所有可能的结尾元素 g in[1,m]，查看 dp[n][g] 的第 x 位是否为1。如果存在，则说明有解。我们记录下第一个找到的 g 作为序列的最后一个元素 a_n。

2. 反向推导整个序列，已知 a_n，当前的总和为 x。那么前 n−1 个元素的和必须是 x−a_n，我们需要找到 a_n−1，它必须是 a_n 的倍数，并且 dp[n−1][a_n−1] 的第 x−a_n 位必须为1，我们从小到大遍历 a_n 的倍数来寻找合适的 a_n−1，以此类推，直到找到 a_1 为止。

具体代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int M = 50;
const int N = M*M; 

using dd = vector<vector<bitset<N + 1>>>;

void solve() {
    int n, m,x;
    cin >> n >> m >> x;

    if (x < n) { // 最小和是n个1，如果x<n则无解
        cout << -1 << endl;
        return;
    }
    dd dp(n + 1, vector<bitset<N + 1>>(m + 1));

    // 基础情况: i = 1
    for (int g = 1; g <= m; ++g) {
        if (g <= x) {
            dp[1][g][g] = 1;
        }
    }

    for (int i = 2; i <= n; ++i) {
        for (int g = 1; g <= m; ++g) { 
            // 遍历所有可能的 a_{i-1} = k，其中 k 是 g 的倍数
            for (int k = g; k <= m; k += g) { 
                // 从 (i-1, k) 状态转移到 (i, g)
                dp[i][g] |= (dp[i-1][k] << g);
            }
        }
    }

    int l = -1;
    for (int g = 1; g <= m; ++g) {
        if (x <= N && dp[n][g][x]) {
            l = g; // 找到了一个可行的结尾 a_n
            break;
        }
    }

    if (l == -1) {
        cout << -1 << endl;
    } else {
  
        vector<int> a(n);
        int c = l; // 当前要找的数
        int r = x; // 剩余的和

        for (int i = n; i >= 1; --i) {
            a[i - 1] = c;
            r -= c;
            if (i > 1) {
                // 寻找 a_{i-1} = p且p 必须是 c 的倍数
                for (int p = c; p <= m; p += c) {
                    if (r >= 0 && r <= N && dp[i - 1][p][r]) {
                        c = p;
                        break;
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
           cout << a[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}