Description
lyk拥有一个区间。
它规定一个区间的价值为这个区间中所有数and起来的值与这个区间所有数or起来的值的乘积。
例如3个数2,3,6。它们and起来的值为2，or起来的值为7，这个区间对答案的贡献为2*7=14。
现在lyk有一个n个数的序列，它想知道所有n*(n+1)/2个区间的贡献的和对1000000007取模后的结果是多少。
例如当这个序列为{3,4,5}时，那么区间[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]的贡献分别为9,0,0,16,20,25。
Solution
这种题很显然要拆位，
每一个数拆开以后，每位对于and操作，有值的点一定是连续一段的，设达到了 ki(第i位) ，这个可以预处理每一个数的每一位，
对于or操作，有值的点一定是从第一个数开始的连续一段，设到达了j，而对ans的贡献就是当前数的每一位，以j作为结尾，以 ki 作为开头的一段是有贡献的。
复杂度： O(nlog(109)2) （做人要有梦想！）
Code
//这个程序是有概率AC的…（卡常），跑了1000ms。
#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)using namespace std;typedef long long LL;typedef long double LB;const int N=100500,mo=1000000007;int read(int &n){ char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;}int n,TT;int f[N][32],a[N];LL ans,er[32],es[N][32];LL F[N][32];int zx[N][32];LL min(LL q,LL w){return q>w?w:q;}bool PX(int q,int w){return f[TT][q]<f[TT][w];}int ef(int w,int q){if(f[w][zx[w][1]]>=q)return 0; int l=1,r=30;TT=0; while(l<r) {int t=(l+r+1)/2; if(f[w][zx[w][t]]<q)l=t; else r=t-1; } return l;}int main(){ LL q,w; er[1]=1;fo(i,2,30)er[i]=er[i-1]<<1; read(n); fo(i,1,n)read(a[i]); fo(I,1,30) {f[0][I]=n+1; fo(i,1,n) if(a[i]&er[I])f[i][I]=min(f[i-1][I],i); else f[i][I]=n+1; } fo(i,1,n) {fo(j,1,30)zx[i][j]=j; TT=i;f[i][0]=0; sort(zx[i]+1,zx[i]+31,PX); fo(j,1,30)F[i][zx[i][j]]=(F[i][zx[i][j-1]]+f[i][zx[i][j]]*er[zx[i][j]])%mo, es[i][zx[i][j]]=(es[i][zx[i][j-1]]+er[zx[i][j]]); } fo(I,1,30) {q=0; fo(i,1,n) {if(a[i]&er[I])q=i; w=zx[i][ef(i,q+1)]; ans=(ans+er[I]*((q+1)*es[i][w]%mo-F[i][w])%mo)%mo; } } printf("%lld\n",(ans+mo)%mo); return 0;}
