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

N.Particle Arts

题目大意

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

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

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

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

Code

#include <bits/stdc++.h>
#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 <= n; i++) cin >> a[i], sum += a[i];
    int cnt0 = 0, cnt1 = 0;
    for(int i = 1; i <= n; i++){
    
        for(int j = 0; j < 15; j++){
    
            if((a[i] >> j) & 1) cnt[j]++; 
        }
    }
    for(int i = 0; i < 15; i++){
    
        for(int j = 1; j <= cnt[i]; j++) b[j] |= (1 << i);
    }
    int f1 = 0;
    for(int i = 1; i <= n; i++){
    
        f1 += (n * b[i] - sum) * (n * b[i] - sum);
    }
    int f2 = n * n * n;
    int gcdd = __gcd(f1, f2);
    //cout << f1 << '@' << f2 << endl;
    long long ans1 = f1 / gcdd, ans2 = f2 / gcdd;
    //cout << (f1 / gcdd) << '/' << (f2 / gcdd) << endl;
    cout << ans1 << '/' << ans2 << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}