灵茶八题 题目解析+核心代码

子数组+w+

1. 由于仅存在加法，即满足交换律和结合律，故可考虑累加单个元素的总贡献
2. 对当前元素g[i]，包含该元素的子数组数为(i + 1) * (n - i + 1)，则该元素的总贡献为(i + 1) * (n - i) * g[i]，枚举所有元素累加即可
   • i起始为1

void solve(){
    int n;
    cin >> n;

    ll res = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        res += 1ll * i * (n - i + 1) * x;
    }

    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13

子数组^w^

类似考虑单个元素总贡献，当元素g[i]的出现次数(i + 1) * (n - i)为奇数时总贡献为g[i]，否则为0，计算异或和即可

void solve(){
    int n;
    cin >> n;

    ll res = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;

        x = (((n - i + 1) * i) & 1) * x;
        res ^= x;
    }

    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

子数组^w+

1. 考虑异或前缀和sx[i]，对任意子数组的异或和可表示为sx[r] ^ sx[l - 1]
2. 考虑二进制拆位，即枚举累加每个二进制位的贡献
3. 对当前位k，相当于在前缀和数组中选取两个元素，使sx[r] ^ sx[l - 1]中该位为1，即sx[r]和sx[l - 1]必须恰好一个1一个0，此时贡献为1 << k
4. 枚举统计前缀和数组中当前位下为1的元素个数cnt，则为0的个数为(n + 1 - cnt)，故存在贡献的子数组的总贡献为cnt * (n + 1 - cnt) * (1 << k)

void solve(){
    int n;
    cin >> n;

    ve sx(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> sx[i];
        sx[i] ^= sx[i - 1];
    }

    ll res = 0;
    for(int k = 0; k < 22; k++){
        int cnt = 0;
        for(int i = 0; i <= n; i++) cnt += sx[i] >> k & 1;
        res += 1ll * cnt * (n + 1 - cnt) * (1 << k);
    }

    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

子数组+w^

1. 考虑前缀和$s[i]$，对任意子数组和可表示为$s[r]-s[l-1]$

2. 考虑二进制拆位，即枚举累加每个二进制位的贡献

3. 对当前$k$位，需要获取所有子数组和该位为1的数量，若为奇数则贡献为$2^k$，否则为0

4. 问题转换为求指定位下所有子数组和该位为1的数量

5. 只考虑低位到$k$位，令所有$s[i]$对$2^{k+1}$取模，从而将$s[r]-s[l-1]$的结果及其$s[r]$和$s[l-1]$压缩到一定连续范围内

6. 当$k=2$时，$s[r]-s[l-1]$产生$k$位为1的结果范围为[100, 111]，考虑减法操作中高位的影响，如1000 - 1 = 111的结果满足条件，故当$s[r]\ge 2^{k+1}$时，在$k+1$位补1，此时结果范围为$[100,111]\cup [1100,1111]$，则$s[l-1]$的范围为

   $[s[r]-111,s[r]-100]\cup [s[r]-1111,s[r]-1100]$

7. 枚举所有$s[r]$，对当前$s[r]$获取$[1,r-1]$中在区间内的$s[l-1]$的个数进行累加，最后得到当前位下所有子数组和该位为1的数量

8. 由于$[1,r-1]$是动态区间，故使用树状数组维护即可

const int N = 2e7 + 10;

ve tr(N);

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

void add(int idx, int val){
    idx++;
    for(int i = idx; i < N; i += lowbit(i)) tr[i] += val;
}

int sum(int x){
    x++;
    int ans = 0;
    while(x > 0){
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

void solve(){
    int n;
    cin >> n;

    ve s(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] += s[i - 1];
    }

    int res = 0;
    for(int k = 0; (1 << k) <= s[n]; k++){
        add(0, 1);

        int cnt = 0;
        for(int i = 1; i <= n; i++){
            int ts = s[i] & ((1 << (k + 1)) - 1);
            if(s[i] >= 1 << (k + 1)) ts |= 1 << (k + 1);

            int r = ts - (1 << k), l = ts - (1 << (k + 1)) + 1;
            cnt += sum(r) - sum(l - 1);
            l -= 1 << (k + 1), r -= 1 << (k + 1);
            cnt += sum(r) - sum(l - 1);

            add(s[i] & ((1 << (k + 1)) - 1), 1);
        }

        if(cnt & 1) res |= 1 << k;

        fill(all(tr), 0);
    }

    cout << res << '\n';
}
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

子序列+w+

1. 由于仅存在加法，即满足交换律和结合律，故可考虑累加单个元素的总贡献
2. 对于元素g[i]，包含该元素的子序列总数为$2^{n-1}$，即总贡献为$2^{n-1}\ast g[i]$
3. 所有元素总贡献为$2^{n-1}\ast sum$

void solve(){
    int n;
    cin >> n;

    ll res = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        res += x;
    }

    for(int i = 0; i < n - 1; i++) res = 2 * res % mod;

    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

子序列^w^

1. 类似可考虑累加异或单个元素的总贡献
2. 当且仅当n = 1存在贡献g[0]，否则$2^{n-1}$为偶数，总贡献为0

void solve(){
    int n;
    cin >> n;

    ve g(n);
    for(int i = 0; i < n; i++) cin >> g[i];

    if(n == 1) cout << g[0] << '\n';
    else cout << 0 << '\n';
}
1
2
3
4
5
6
7
8
9
10

子序列^w+

1. 考虑二进制拆位，即枚举累加每个二进制位的贡献
2. 对于当前位k，若所有元素都为0，则总贡献为0
3. 若存在元素为1，设数量为c，可用数学归纳法证明从c个数中选偶数个数和奇数个数的方案数都为$2^{c-1}$，再算上0可得异或和为0和为1的子序列数都为$2^{n-1}$
4. 则此时该位总贡献为$2^{n-1}\ast 2^k$

void solve(){
    int n;
    cin >> n;

    ve g(n);
    for(int i = 0; i < n; i++) cin >> g[i];

    ll res = 0;
    for(int k = 0; k < 30; k++){
        bool ok = false;
        for(int i = 0; i < n; i++){
            if(g[i] >> k & 1){
                ok = true;
                break;
            }
        }

        if(ok) res += 1 << k;
    }

    for(int i = 0; i < n - 1; i++) res = 2 * res % mod;

    cout << res << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

子序列+w^

1. 考虑枚举累加每个子序列和的可能值的贡献
2. 对当前序列数和sum，得到该和的方案数为奇数时贡献为sum，否则为0
3. 考虑使用01背包推导序列数和的方案数的奇偶性

void solve(){
    int n;
    cin >> n;

    int m = 1 << 16;
    ve dp(m + 1);
    dp[0] = 1;

    for(int i = 0; i < n; i++){
        int v;
        cin >> v;

        for(int j = m; j >= v; j--){
            dp[j] = dp[j] ^ dp[j - v];
        }
    }

    int res = 0;
    for(int i = 0; i <= m; i++){
        if(dp[i]){
            res ^= i;
        }
    }

    cout << res << '\n';
}
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