Main » 2013 October 30 » 「Nescafé26」Rainbow的信号
5:29 AM 「Nescafé26」Rainbow的信号 |
一位位算#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define B 30 #define N 100010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; LL Or,And,Xor,tor,tand,txor; int n,back[B][N],len[B][N],nxt[B][N],bit[N][B]; int main() { scanf("%d",&n); int bitL=0,i,j; FOR(i,1,n) { int tt; scanf("%d",&tt); int tmp=tt; while (tmp) { bit[i][0]++; bit[i][bit[i][0]]=tmp%2; tmp/=2; } if (bit[i][0]>bitL) bitL=bit[i][0]; } FOR(i,1,bitL) { back[i][n+1]=0;len[i][n+1]=0;nxt[i][n+1]=n+1; ROF(j,n,1) { if (bit[j][i]==0) { len[i][j]=0; nxt[i][j]=nxt[i][j+1]; back[i][j]=back[i][j+1]; } else { len[i][j]=len[i][j+1]+1; nxt[i][j]=j; int cnt=n-j; //if (j==n) back[i][j]=1; //else back[i][j]=cnt-back[i][j+1]+1; } } } Or=0;Xor=0;And=0;LL po=1; FOR(i,1,bitL) { tor=0;txor=0;tand=0; FOR(j,1,n) { //or if (nxt[i][j]==j) { tor++; tor+=(n-j)*2; }else tor+=(n-nxt[i][j]+1)*2; //and if (len[i][j]>0) tand+=1+(len[i][j]-1)*2; //xor if (bit[j][i]==1) { txor+=back[i][j]*2; txor--; }else { txor+=back[i][j]*2; } } Or+=po*tor;Xor+=po*txor;And+=po*tand; po*=2; } double tot=(LL)n*(LL)n; printf("%.3lf ",(double)Xor/tot); printf("%.3lf ",(double)And/tot); printf("%.3lf\n",(double)Or/tot); } |
|
|
| Total comments: 0 | |