Magic Formulas

发表于 更新于 分类于 ，

    给出n个数的序列$p_1,p_2,\cdots,p_n$，求$\bigoplus \limits_{i=1}^n (p_i\bigoplus \limits_{j=1}^n i \mod j)$

Magic Formulas

Created by LXC on Sun May 7 11:46:36 2023

https://codeforces.com/problemset/problem/424/C

ranting: 1600

tag: math

题意

给出n个数的序列$p_1,p_2,\cdots,p_n$，求$\bigoplus \limits_{i=1}^n (p_i\bigoplus \limits_{j=1}^n i \mod j)$

题解

找一下规律，当n = 5时

i \ j 1 2 3 4 5
1 0 1 1 1 1
2 0 0 2 2 2
3 0 1 0 3 3
4 0 0 1 0 4
5 0 1 2 1 0

对于固定的j，i%j呈现周期变化

根据异或的性质，对于多个出现的相同的数，出现次数为奇数相当于异或了一次，出现了偶数次则相当于没有异或。

当n能被i整除时，考虑$\lfloor\frac{n}{i}\rfloor$的奇偶性。如果出现奇数次则对于[0,i-1]都出现了一次。

当n不能能被i整除时，存在余数[1,n%i]，$\lfloor\frac{i}{j}\rfloor$ 为偶数则[1,n % i]出现一次，否则[0] and [n%i+1, i-1]出现了一次。

这里我们做了多次区间修改，最后需要知道每个值出现了多少次。
这个完全可以使用差分数组做到。

另一种做法可以预处理出$f_i$为0到i的异或和。

初始化答案为0
每一个i，n/i为奇数则答案异或上$p_i\oplus f_{i-1} \oplus f_{n \mod i}$；n/i为偶数则答案异或上$p_i \oplus f_{n \mod i}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    int ans = 0;
    for (int& i : a)
        cin >> i, ans ^= i;
    vector<int> d(n + 5);
    for (int i = 1; i <= n; i++) {
        int o = n / i % 2;
        if (n % i == 0) {
            if (o) {  // [0, i-1]
                d[0]++;
                d[i]--;
            }
        } else {
            if (o) {  // [0] and [n%i+1, i-1]
                d[0]++;
                d[1]--;
                d[n % i + 1]++;
                d[i]--;
            } else {  // [1, n%i]
                d[1]++;
                d[n % i + 1]--;
            }
        }
    }
    int c = 0;
    for (int i = 0; i <= n; i++) {
        c += d[i];
        if (c % 2)
            ans ^= i;
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}