这道题好难

原题

E. Expected Power

提示

Hint 1

试着找 f(S) 的期望值而不是

Hint 2

从f(S)的二进制表示中找规律来求

代码1

对答案代码做了注释

#include <bits/stdc++.h>
using namespace std;const int mod = 1e9+7, N = 2e5 + 10;// 最高只有1023, 小于等于2的10次方
const int bits = 11;int n;
int a[N],p[N];// 快速幂
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);
}// 10000的逆元
const int inverse_1e4 = inv(10000);int dp[bits][bits][2][2];void transition(int a, int p)
{
//	概率是多少, 也就是一万分之 pp = (1ll * p * inverse_1e4) % mod;int negp = mod + 1 - p;//	将 a 的二进制形式存入数组int bin[bits];for(int i = 0; i < bits; i ++ ){bin[i] = a & 1;a >>= 1;}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];}}
}void solve()
{cin >> n;for (int i = 0; i < n; i ++) cin >> a[i];for (int i = 0; i < n; i ++) cin >> p[i];//	初始化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 ++ ){int pw2 = (1ll << (i + j)) % mod;ans += (1ll * pw2 * dp[i][j][1][1]) % mod;ans %= mod;
//			用后就清空for(int k : {0,1})for(int l : {0,1}) dp[i][j][k][l] = 0;}}cout << ans << "\n";
}signed main()
{int t;cin >> t;while(t--){solve();}
}