SPOJ:OR(位运算&数学期望)

Given an array of N integers A₁, A₂, A₃…A_N. If you randomly choose two indexes i ,j such that 1 ≤ i < j ≤ N, what is the expected value of A_i | A_j?

Input

First line contains an integer T, the number of test cases. Each test case consists of two lines. First line denotes the size of array, N and second line contains N integers forming the array.
1 ≤ T ≤ 10
2 ≤ N ≤ 100,000
0 ≤ Ai < 2³¹

Output

For each test case, print the answer as an irreducible fraction. Follow the format of the sample output.
The fraction p/q (p and q are integers, and both p ≥ 0 and q > 0 holds) is called irreducible, if there is no such integer d > 1 that divides both p and q separately.

Example

Input:

2

2

0 0

3

1 2 3

Output:

0/1

3/1

题意：给定一个数列a[]，求任意两个数a[i]和a[j]的或运算的期望（i!=j）。

思路：此类题已经是套路了，就是每一位分别看，统计为一位为1和为0的个数。然后根据XOR，或者OR的性质采取相应的措施。

OR的话，就是第i位的贡献是：(C(n,2)-C(num[i],2))/C(n,2)*(1<<i) 。num[i]是第i位为0的个数。

(注意，用unsigned long long)

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll unsigned long long

using namespace std;

ll F,P,G,num[],N,a,b,c,i,j;

int main()

{

    int T,x; scanf("%d",&T);

    while(T--){

        scanf("%lld",&N);

        F=; P=(N-)*N/;

        c=N*(N-)/;

        for(i=;i<;i++) num[i]=;

        for(i=;i<=N;i++){

            scanf("%d",&x);

            for(j=;j<;j++) if(x&(<<j)) num[j]++;

        }

        for(i=;i<;i++){

            F+=(P-(N-num[i])*(N-num[i]-)/)*(1LL<<i);

        }

        G=__gcd(F,P);

        F/=G; P/=G;

        printf("%lld/%lld\n",F,P);

    }

    return ;

}

巴特西

SPOJ:OR(位运算&数学期望)

Input

Output

Example

最新文章

热门文章