“蔚来杯“2022牛客暑期多校训练营4 N.Particle Arts 规律 方差

N.Particle Arts 题目大意

给定序列 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​，每当两个元素 a a a和 b b b相撞后会湮灭并产生两个新元素 a & b a \& b a&b和 a ∣ b a | b a∣b。若干次碰撞后，方差会收敛。求收敛后的方差。

首先可以发现，任意两个元素相撞变化后，不会引起总和的变化，因此均值是不变的。

那么考虑求经过无限此碰撞后生成的新序列，容易发现因为或操作的性质，二进制下为 1 1 1的位不会消失，那么无限次或操作会将为 1 1 1的位向同一数字靠拢。于是直接按位统计后生成新序列计算即可。

如果使用公式 E ( x 2 ) − E 2 ( x ) E(x^2) - E^2(x) E(x2)−E2(x)，需要继续推式子；但可以直接怼上方差公式，但是又会爆long long，那么可以在运算过程中全部使用__int128计算，最后转long long输出。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int __int128
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
long long a[N], b[N], cnt[20];

inline void solve(){
    long long n = 0, sum = 0; cin >> n;
    for(int i = 1; i > a[i], sum += a[i];
    int cnt0 = 0, cnt1 = 0;
    for(int i = 1; i  j) & 1) cnt[j]++; 
        }
    }
    for(int i = 0; i