E. Expected Power 详细题解

题目回顾

给定数组 $a_1,a_2,\dots,a_n$ 和概率数组 $p_1,p_2,\dots,p_n$，每个元素 $a_i$ 以概率 $\frac{p_i}{10^4}$ 被选入集合 $S$。 设 $f(S)$ 为集合 $S$ 的异或和，求 $E\left[(f(S))^2\right]$，答案对 $10^9+7$ 取模。

---

一、核心数学推导

1. 平方展开

设最终异或和为 $x = f(S)$，其二进制表示为 $x = \sum_{k=0}^{10} b_k \cdot 2^k$（因为 $a_i \le 1023=2^{10}-1$，仅需11位）。

平方展开：

$$x^2 = \left( \sum_{i=0}^{10} b_i 2^i \right) \left( \sum_{j=0}^{10} b_j 2^j \right) = \sum_{i=0}^{10}\sum_{j=0}^{10} b_i b_j \cdot 2^{i+j} $$

对两边取期望：

$$E[x^2] = \sum_{i=0}^{10}\sum_{j=0}^{10} 2^{i+j} \cdot E[b_i b_j] $$

关键结论

$E[b_i b_j]$ 就是第 $i$ 位和第 $j$ 位同时为 1 的概率，我们只需要求这个概率即可。

2. 位对状态 DP

因为异或的每一位独立，我们对每一对位 $(i,j)$ 单独维护 DP：

• $dp[i][j][x][y]$：当前第 $i$ 位异或结果为 $x$，第 $j$ 位异或结果为 $y$ 的概率。
• 初始状态：$dp[i][j][0][0] = 1$（未选任何数，两位都是 0）。

3. 转移规则

加入一个数 $a$：

• 它的第 $i$ 位是 $bit_i$
• 它的第 $j$ 位是 $bit_j$

转移：

• 不选这个数：状态不变
• 选这个数：状态变为 $(x\oplus bit_i,\ y\oplus bit_j)$

最终答案：

$$ans = \sum_{i=0}^{10}\sum_{j=0}^{10} dp[i][j][1][1] \cdot 2^{i+j} $$

---

二、标程代码详细解析

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

const int mod = 1e9 + 7;
const int bits = 11; // a_i ≤ 1023，仅需 0~10 共11位
int dp[bits][bits][2][2];   // 核心DP：dp[i][j][x][y]

// 快速幂：求逆元
int fast_exp(int b, int e, int mod) {
	int ans = 1;
	while(e) {
		if(e&1) ans = (1ll*ans*b) % mod;
		b = (1ll*b*b) % mod;
		e >>= 1;
	}
	return ans;
}

// 费马小定理求逆元
int inv(int n) {
	return fast_exp(n, mod-2, mod);
}

const int inverse_1e4 = inv(10000); // 1e4的逆元，固定预计算

// 状态转移：加入数字 a，概率 p
void transition(int a, int p) {
	// 真实概率 = p / 1e4
	p = (1ll * p * inverse_1e4) % mod;
	int negp = (mod + 1 - p) % mod; // 不选的概率 1-p

	// 取出 a 的每一位
	int bin[bits];
	for(int i = 0; i < bits; i++) {
		bin[i] = a & 1;
		a >>= 1;
	}

	// 对每一对 (i,j) 转移
	for(int i = 0; i < bits; i++) {
		for(int j = 0; j < bits; j++) {
			int temp[2][2];
			// 新状态 = 不选的情况 + 选的情况
			for(int k : {0,1}) for(int l : {0,1})
				temp[k][l] = (1ll*dp[i][j][k][l] * negp  // 不选
				            + 1ll*dp[i][j][k^bin[i]][l^bin[j]] * p) % mod; // 选
			// 覆盖更新
			for(int k : {0,1}) for(int l : {0,1})
				dp[i][j][k][l] = temp[k][l];
		}
	}
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
    	int n; cin >> n;
    	int a[n], p[n];
    	for(int i=0; i<n; i++) cin >> a[i];
    	for(int i=0; i<n; i++) cin >> p[i];

    	// DP初始化：所有位对初始都是 (0,0)，概率1
    	for(int i=0; i<bits; i++)
    		for(int j=0; j<bits; j++)
    			dp[i][j][0][0] = 1;

    	// 逐个元素转移
    	for(int i=0; i<n; i++)
    		transition(a[i], p[i]);

    	// 计算答案
    	int ans = 0;
    	for(int i=0; i<bits; i++) {
    		for(int j=0; j<bits; j++) {
    			// 2^(i+j)
    			int pw2 = (1ll << (i+j)) % mod;
    			// 累加 E[b_i b_j] * 2^(i+j)
    			ans = (ans + 1ll * pw2 * dp[i][j][1][1]) % mod;
    			// 清空DP，准备下一组测试用例
    			for(int k : {0,1}) for(int l : {0,1})
    				dp[i][j][k][l] = 0;
    		}
    	}
    	cout << ans << '\n';
    }
	return 0;
}

---

三、核心要点总结

1. 数学核心

$$E[x^2] = \sum_{i,j} 2^{i+j} \cdot P(\text{bit }i=1 \text{ 且 } bit\ j=1) $$

2. DP 状态

• $dp[i][j][x][y]$：第 $i$ 位为 $x$、第 $j$ 位为 $y$ 的概率
• 大小：$11 \times 11 \times 2 \times 2 = 484$，极小常数

3. 转移

• 选：概率 $p$，状态异或当前数的对应位
• 不选：概率 $1-p$，状态不变

4. 复杂度

$O(\sum n \times 11 \times 11) = O(121 \sum n)$ 完全可以通过 $\sum n \le 2 \times 10^5$。

---

四、样例验证（第一个样例）

• $a = [1,2]$，概率各 $1/2$
• 最终 $dp[0][0][1][1] = 1/4$，$dp[1][1][1][1] = 1/4$，$dp[0][1][1][1] = dp[1][0][1][1] = 1/4$
• 答案：

$$1 \cdot \frac14 + 4 \cdot \frac14 + (2+2)\cdot\frac14 = \frac{14}{4} = \frac72 $$

对 $1e9+7$ 取模为 $500000007$，与样例一致。

---

最终总结

1. 平方展开：把 $E[x^2]$ 拆成位对期望之和
2. 位对 DP：维护每一对 $(i,j)$ 的异或状态概率
3. 转移简单：选/不选两种情况
4. 复杂度极低：$O(n \cdot 11^2)$，标准高效解法