OR

原题：OR

原题大意

给出n个数A1, A2…,AN, 任意选择两个数i,j(1 <= i < j <= N),问Ai|Aj的期望值是多少。
以既约分数的形式输出。

算法分析

如果暴力需要n^2，会超时，所以考虑每一位，前i-1个数里，第j位是0的个数为cnt，如果第i个数的第j位是1，那么贡献为(1 << j) (i-1)，否则贡献为cnt (1 << j)。如果直接算出分子除以分母会爆long long int，所以记录余数然后两次gcd求出结果。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
int T;
ll cnt[40];
ll x, y, n;
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        mem(cnt, 0);
        x = 0LL;
        cin >> n;
        y = n * (n-1) / 2;
        ll t, tt = 0LL;
        for(int i = 1; i <= n; i++){
            cin >> t;
                for(int j = 0; j <= 33; j++){
                    if((1LL<<j) & t) 
                        {
                            x += (i-1) * (1LL<<j);
                            cnt[j]++;
                        }
                    else {
                        x += cnt[j]*(1LL<<j);
                    }
                }
            if(x > y){
                tt += x/y;
                x %= y;
            }
        }
        ll g = gcd(x, y);
        x /= g, y /= g;
        x += y * tt;
        g = gcd(x, y);
        cout << x/g << "/" << y/g << endl;
    }
    return 0;
}