给定序列 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
输出。
#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 <= 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;
}