A – 神奇的位运算

想了半天，最后一看是离线来维护，直接吐血。

首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和，一种方式是使用主席树进行维护，另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或：我们把每个数往尽可能近的地方塞，这个时候就需要用 map 来判断要不要移动。

// xor.cpp
#include <bits/stdc++.h>
#define ull unsigned int

using namespace std;

const int MAX_N = 3e5 + 200;

int n, m, prefix[MAX_N][32];
ull ai[MAX_N], pre[MAX_N], nodes[MAX_N], anses[MAX_N];
unordered_map<ull, int> pos;
vector<pair<int, int> /**/> vec[MAX_N];

int lowbit(int x) { return x & (-x); }

void update(int x, ull val)
{
    for (; x <= n; x += lowbit(x))
        nodes[x] ^= val;
}

int query(int x, ull ret = 0)
{
    for (; x; x -= lowbit(x))
        ret ^= nodes[x];
    return ret;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%u", &ai[i]), pre[i] = pre[i - 1] ^ ai[i];
    scanf("%d", &m);
    for (int i = 1, l, r; i <= m; i++)
        scanf("%d%d", &l, &r), vec[r].push_back(make_pair(l, i)), anses[i] = pre[r] ^ pre[l - 1];
    ull tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (pos[ai[i]])
            update(pos[ai[i]], ai[i]);
        else
            tot ^= ai[i];
        update(pos[ai[i]] = i, ai[i]);
        for (int idx = 0, siz = vec[i].size(); idx < siz; idx++)
            anses[vec[i][idx].second] ^= tot ^ query(vec[i][idx].first - 1);
    }
    for (int i = 1; i <= m; i++)
        printf("%u\n", anses[i]);
    return 0;
}

C – 奇妙计数题

看到题先大力反演：

\[ \begin{aligned} \text{ans} &= \sum_{i = 1}^n \sum_{j = 1}^n (a_i, a_j) \cdot (i, j) \\ &= \sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n (a_i, a_j) [(i, j) = d] \\ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} (a_{id}, a_{jd}) [(i, j) = 1] \\ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} (a_{id}, a_{jd}) \sum_{x|i, x|j} \mu(x) \\ &= \sum_{d = 1}^n d \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(x) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} (a_{id}, a_{jd}) [x|i] [x|j] \\ &= \sum_{d = 1}^n d \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(x) \sum_{i = 1}^{\lfloor \frac{n}{dx} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{dx} \rfloor} (a_{idx}, a_{jdx}) \end{aligned} \]

设置最后一部分，然后我们来筛下：

\[\begin{aligned} f(dx) &= \sum_{i = 1}^{\lfloor \frac{n}{dx} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{dx} \rfloor} (a_{idx}, a_{jdx}) \\ f(x) &= \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} (a_{ix}, a_{jx}) \\ &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} d \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [(a_{ix}, a_{jx}) = d] \end{aligned}\]

如何把最后一个地方转化掉？我们没法直接用单位元卷积，因为条件不一样。但是稍作转化：

\[ \sum_{d|T, T|x} \mu(\frac{T}{d}) = [x = d] \]

就相当于单位\(1\)乘上了\(d\)所得到的。有了这个之后，我们带入即可：

\[\begin{aligned} f(x) &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} d \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [(a_{ix}, a_{jx}) = d] \\ &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} d \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{d|T, T|(a_{ix}, a_{jx})} \mu(\frac{T}{d}) \\ &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{d|T, T|(a_{ix}, a_{jx})} d \mu(\frac{T}{d}) \end{aligned}\]

好像要拿到\(\varphi\)卷积了！调换一下：

\[ \begin{aligned} f(x) &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{d|T} d \mu(\frac{T}{d}) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [T|(a_{ix}, a_{jx})] \\ &= \sum_{d = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{d|T} d \mu(\frac{T}{d}) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [T|a_{ix}] [T|a_{jx}] \\ &= \sum_{T = 1}^{n} \varphi(T) (\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [T|a_{ix}])^2 \end{aligned}\]

差不多就可以筛了，只不过好像只能用埃式筛法，因为每一个因子都要到位。带回答案应该就很简单了。

// gcd.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 2000, mod = 1e9 + 7;

int phi[MAX_N], mu[MAX_N], primes[MAX_N], tot, f[MAX_N], n, ai[MAX_N], bucket[MAX_N];
bool vis[MAX_N];
vector<int> fac[MAX_N], tmp;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    mu[1] = 1, phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            primes[++tot] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= tot && 1LL * i * primes[j] <= n; j++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                mu[i * primes[j]] = 0;
                break;
            }
            phi[i * primes[j]] = phi[i] * phi[primes[j]];
            mu[i * primes[j]] = -mu[i];
        }
    }
    // \Theta(n \log n);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)
            fac[j].push_back(i);
    // process the f(x), by enumerating size d;
    for (int d = 1; d <= n; d++)
    {
        for (int i = d; i <= n; i += d)
            for (vector<int>::iterator it = fac[ai[i]].begin(); it != fac[ai[i]].end(); it++)
                bucket[*it]++, tmp.push_back(*it);
        for (vector<int>::iterator it = tmp.begin(); it != tmp.end(); it++)
            if (bucket[*it])
                f[d] = (1LL * f[d] + 1LL * bucket[*it] * bucket[*it] % mod * phi[*it] % mod) % mod, bucket[*it] = 0;
        tmp.clear();
    }
    int ans = 0;
    for (int d = 1; d <= n; d++)
        for (int x = 1; x <= (n / d); x++)
            ans = (1LL * ans + 1LL * d * mu[x] % mod * f[d * x] % mod + mod) % mod;
    printf("%d\n", ans);
    return 0;
}