灵茶八题

仅仅是几个字的区别，会导致截然不同的做法，也许这就是算法之美吧！

题单合集

• 子数组 +w+ 给你一个长为 n 的数组 a，输出它的所有连续子数组的元素和的元素和。
• 子数组 ^w^ 给你一个长为 n 的数组 a，输出它的所有连续子数组的异或和的异或和。
• 子数组 ^w+ 给你一个长为 n 的数组 a，输出它的所有连续子数组的异或和的和。
• 子数组 +w^ 给你一个长为 n 的数组 a，输出它的所有连续子数组的元素和的异或和。
• 子序列 +w+ 给你一个长为 n 的数组 a，输出它的所有非空子序列的元素和的元素和。
• 子序列 ^w^ 给你一个长为 n 的数组 a，输出它的所有非空子序列的异或和的异或和。
• 子序列 ^w+ 给你一个长为 n 的数组 a，输出它的所有非空子序列的异或和的和。
• 子序列 +w^ 给你一个长为 n 的数组 a，输出它的所有非空子序列的元素和的异或和。

---

• LQ231227T5 异或与求和
• Abc365E - Xor Sigma Problem

题解

注：下标从 $0$ 开始。二进制的最低位是第 $0$ 位。

贡献法

考虑 $a[i]$ 对答案的贡献：

• 子数组 +w+ 子数组元素和的元素和：包含 $a[i]$ 的子数组的左端点有 $i+1$ 个，右端点有 $n-i$ 个，根据乘法原理，有 $(i+1)\cdot(n-i)$ 个子数组包含 $a[i]$，所以 $a[i]$ 对答案的贡献为 $(i+1)\cdot(n-i)\cdot a[i]$。
• 子数组 ^w 子数组异或和的异或和：同上。更强的结论是：
  • 当 $n$ 是偶数时，$i+1$ 和 $n-i$ 必定一奇一偶，所以 $(i+1)(n-i)$ 是偶数，答案为 $0$。
  • 当 $n$ 是奇数时，如果 $i$ 为奇数，那么 $i+1$ 和 $n-i$ 都是偶数；如果 $i$ 为偶数，那么 $i+1$ 和 $n-i$ 都是奇数，所以只有 $i$ 为偶数时 $(i+1)(n-i)$ 才是奇数。所以，答案为所有偶数下标的 $a[i]$ 的异或和。
• 子序列 +w+ 子序列的元素和的元素和：包含 $a[i]$ 的子序列有 $2^{n-1}$ 个。所以 $a[i]$ 对答案的贡献为 $2^{n-1}\cdot a[i]$。所以答案为 $2^{n-1}\cdot \sum a[i]$。
• 子序列 ^w 子序列的异或和的异或和：
  • 当 $n=1$ 时，答案为 $a[0]$。
  • 当 $n\ge 2$ 时，由于 $2^{n-1}$ 是偶数，所以答案为 $0$。

    private static String solve() {
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long c = (i + 1L) * (n - i);
            ans += c * a[i];
        }
        return String.valueOf(ans);
    }

    private static String solve() {
        if (n % 2 == 0) return "0";
        long ans = 0;
        for (int i = 0; i < n; i += 2) {
            ans ^= a[i];
        }
        return String.valueOf(ans);
    }

    private static String solve() {
        long sum = 0;
        // 2^{n-1}
        long cnt = 1;
        for (int i = 0; i < n; i++) {
            sum = (sum + a[i]) % MOD;
            if (i > 0) cnt = (cnt * 2) % MOD;
        }
        long ans = sum * cnt % MOD;
        return String.valueOf(ans);
    }

    private static String solve() {
        if (n == 1) {
            return String.valueOf(a[0]);
        }
        return "0";
    }

二进制拆位

• 子数组 ^w+ 子数组异或和的元素和：
  • 提示：如果数组中只有 $0$ 和 $1$，要怎么做？
  • 相当于计算有多少个子数组，异或和等于 $1$。
  • 计算前缀异或和数组 $s$（长为 $n+1$），相当于从 $s$ 中选两个数，异或等于 $1$。
  • 这两个数必须恰好一个是 $1$，另一个是 $0$。
  • 假设 $s$ 中有 $c$ 个 $1$，那么就有 $n+1-c$ 个 $0$，所以答案为 $c\cdot(n+1-c)$。
  • 一般地，统计 $s$ 中第 $k$ 位的 $1$ 的个数 $c$，那么这一位对答案的贡献是 $c\cdot(n+1-c)\cdot 2^k$。
• 子序列 ^w+ 子序列异或和的元素和：
  • 如果第 $k$ 位都是 $0$，那么对答案的贡献是 $0$。
  • 如果第 $k$ 位有 $c$ 个 $1$，用数学归纳法可以证明，从 $c$ 个数中选偶数个数的方案数是 $2^{c-1}$，选奇数个数的方案数也是 $2^{c-1}$。再算上 $0$，那么异或和为 $0$ 的子序列有 $2^{n-1}$ 个，异或和为 $1$ 的子序列也有 $2^{n-1}$ 个，所以这一位的贡献是 $2^{n-1}\cdot 2^k$。

    private static String solve() {
        long ans = 0;
        for (int k = 0; k < 31; k++) {
            int cnt1 = 0;
            int xor = 0;
            for (int v : a) {
                xor ^= v >> k & 1;
                cnt1 += xor;
            }
            ans += (cnt1 * (n + 1L - cnt1)) << k;
        }
//        // 去掉长度为 1 的子数组
//        for (int v : a) ans -= v;
        return String.valueOf(ans);
    }

    private static String solve() {
        // 2^{n-1}
        long cnt = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0) cnt = (cnt * 2) % MOD;
        }

        long ans = 0;
        for (int j = 0; j < 32; j++) {
            int bit = 0;
            for (int i = 0; i < n; i++) {
                bit |= a[i] >> j & 1;
            }
            if (bit > 0) {
                ans += (1 << j) * cnt % MOD;
                ans %= MOD;
            }
        }
        return String.valueOf(ans);
    }

0-1 背包

• 子序列 +w^ 子序列元素和的异或和：
  • 定义 $f[i][j]$ 表示从前 $i$ 个数中选出元素和为 $j$ 的方案数的奇偶性。
  • 初始值 $f[0][0]=1$，其余为 $0$。
  • 状态转移方程为 $f[i+1][j]=f[i][j]\oplus f[i][j-a[i]]$。
  • 答案为 $f[n][j]=1$ 的 $j$ 的异或和。
  • 第一个维度可以优化掉。

    private static String solve() {
        int m = 1 << 16;
        int[] dp = new int[m + 1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            int v = a[i];
            for (int j = m; j >= v; j--) {
                dp[j] = dp[j] ^ dp[j - v];
            }
        }

        int ans = 0;
        for (int i = 0; i <= m; i++) {
            if (dp[i] != 0) {
                ans ^= i;
            }
        }
        return String.valueOf(ans);
    }

借位拆位

• 子数组 +w^ 子数组元素和的异或和：
  • 推荐先完成 ARC092D - Two Sequences
  • 计算出前缀和数组 $s$。
  • 考虑所有的【两个前缀和相减】的结果，二进制从低到高第 $k$ 位有多少个 $1$。
  • 例如 $k=2$ 时，相当于减法的结果的低 $3$ 位在 $[100,111]$ 中。但如果只考虑前缀和的低 $3$ 位，$1000-1=111$ 本来应该满足条件，但是只取低 $3$ 位就变成 $0-1$ 了。
  • 如果前缀和 $\ge 2^3$，我们可以在取低 $3$ 位后补一个 $2^3$，这样 $1000-1=111$ 就是满足要求的。
  • 但是，还有可能出现 $1111-1=1110$ 这样的情况，所以减法的结果应当在 $[100,111]\cup [1100,1111]$ 中。
  • 这可以用树状数组/名次树维护统计。

    static class Fenwick {
        int n;
        int[] tr;

        public Fenwick(int n) {
            this.n = n;
            tr = new int[n + 1];
        }

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

        void add(int pos, int val) {
            pos++;
            for (; pos <= n; pos += lb(pos)) tr[pos] += val;
        }

        int query(int pos) {
            pos++;
            int ret = 0;
            for (; pos > 0; pos -= lb(pos)) ret += tr[pos];
            return ret;
        }
    }

    private static String solve() {
        int ans = 0;
        for (int k = 0; (1L << k) <= s[n]; k++) {
            Fenwick fen = new Fenwick(s[n]);
            fen.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 += fen.query(r) - fen.query(l - 1);
                l -= 1 << (k + 1);
                r -= 1 << (k + 1);
                cnt += fen.query(r) - fen.query(l - 1);

                fen.add(s[i] & ((1 << (k + 1)) - 1), 1);
            }
            if ((cnt & 1) == 1) ans |= 1 << k;
        }
        return String.valueOf(ans);
    }

名次树 https://www.luogu.com.cn/record/124708147

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"time"
)

// https://space.bilibili.com/206214
type node struct {
	lr       [2]*node
	priority uint
	key      int
	keyCnt   int
	subCnt   int
}

func (o *node) size() int {
	if o != nil {
		return o.subCnt // 汇总
	}
	return 0
}

func (o *node) maintain() {
	o.subCnt = o.keyCnt + o.lr[0].size() + o.lr[1].size()
}

func (o *node) rotate(d int) *node {
	x := o.lr[d^1]
	o.lr[d^1] = x.lr[d]
	x.lr[d] = o
	o.maintain()
	x.maintain()
	return x
}

type treap struct {
	rd   uint
	root *node
}

func (t *treap) fastRand() uint {
	t.rd ^= t.rd << 13
	t.rd ^= t.rd >> 17
	t.rd ^= t.rd << 5
	return t.rd
}

func (t *treap) size() int { return t.root.size() }

func (t *treap) _put(o *node, key int) *node {
	if o == nil {
		o = &node{priority: t.fastRand(), key: key, keyCnt: 1}
	} else if d := o.cmp(key); d >= 0 {
		o.lr[d] = t._put(o.lr[d], key)
		if o.lr[d].priority > o.priority {
			o = o.rotate(d ^ 1)
		}
	} else {
		o.keyCnt++
	}
	o.maintain()
	return o
}

func (t *treap) put(key int) { t.root = t._put(t.root, key) }

func (t *treap) _delete(o *node, key int) *node {
	if o == nil {
		return nil
	}
	if d := o.cmp(key); d >= 0 {
		o.lr[d] = t._delete(o.lr[d], key)
	} else {
		if o.keyCnt > 1 {
			o.keyCnt--
		} else {
			if o.lr[1] == nil {
				return o.lr[0]
			}
			if o.lr[0] == nil {
				return o.lr[1]
			}
			d = 0
			if o.lr[0].priority > o.lr[1].priority {
				d = 1
			}
			o = o.rotate(d)
			o.lr[d] = t._delete(o.lr[d], key)
		}
	}
	o.maintain()
	return o
}

func (t *treap) delete(key int) { t.root = t._delete(t.root, key) }

func newTreap() *treap { return &treap{rd: uint(time.Now().UnixNano())/2 + 1} }

func (o *node) cmp(a int) int {
	b := o.key
	if a == b {
		return -1
	}
	if a < b {
		return 0
	}
	return 1
}

func (t *treap) min() (min *node) {
	for o := t.root; o != nil; o = o.lr[0] {
		min = o
	}
	return
}

func (t *treap) max() (max *node) {
	for o := t.root; o != nil; o = o.lr[1] {
		max = o
	}
	return
}

// < key 的元素个数
func (t *treap) rank(key int) (kth int) {
	for o := t.root; o != nil; {
		switch c := o.cmp(key); {
		case c == 0:
			o = o.lr[0]
		case c > 0:
			kth += o.lr[0].size() + o.keyCnt
			o = o.lr[1]
		default:
			kth += o.lr[0].size()
			return
		}
	}
	return
}

func solve(a []int) (ans int) {
	n := len(a)
	sum := make([]int, n+1)
	for i, v := range a {
		sum[i+1] = sum[i] + v
	}

	for k := 0; k < 30; k++ {
		l1, r1, l2, r2 := 1<<k, 1<<(k+1)-1, 3<<k, 1<<(k+2)-1
		cnt := 0
		t := newTreap()
		for _, x := range sum {
			s := x & r1
			if s != x {
				s |= 1 << (k + 1)
			}
			cnt += t.rank(s-l1+1) - t.rank(s-r1) + t.rank(s-l2+1) - t.rank(s-r2)
			t.put(x & r1)
		}
		ans += cnt & 1 << k
	}
	return ans
}

func run(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()

	var n int
	Fscan(in, &n)
	a := make([]int, n)
	for i := range a {
		Fscan(in, &a[i])
	}

	Fprint(out, solve(a))
}

 func runBF(_r io.Reader, _w io.Writer) {
	 in := bufio.NewReader(_r)
	 out := bufio.NewWriter(_w)
	 defer out.Flush()
	var n, ans int
	Fscan(in, &n)
	a := make([]int, n)
	for i := range a {
		Fscan(in, &a[i])
	}
	for l := range a {
		sum := 0
		for r := l; r < len(a); r++ {
			v := a[r]
			sum += v
			ans ^= sum
		}
	}
	Fprint(out, ans)
}

func main() { run(os.Stdin, os.Stdout) }

（全文完）