hdu5921 Binary Indexed Tree

题目链接

把题目要求的写成下面的式子，其中$f_x$为$x$的二进制中1的个数，lcp为最长公共前缀中1的个数。 $$ANS=\frac{\sum _{r=0}^n\sum _{l=0}^n(f_l+f_r-2f_{lcp(l,r)})}{2}$$ $$=(n+1)\sum _{r=0}^n{f}_r-\sum _{r=1}^n\sum _{l=1}^n(f_{lcp(l,r)})$$

那我们先枚举每一个位置选算正贡献：设当前枚举到的位置为x，分两种情况： 1.高位都取到了最大值，那么 这一位必须能放1才有贡献，低位可以随便放。 2.高位没有都取到最大值，那么这一位就一定能放1，且低位可以随便放。 这样算出来的就是$\sum _{l=1}^n{f}_l$了。 那再算一下$\sum _{r=1}^n\sum _{l=1}^n(f_{lcp(l,r)})$: 还是枚举每一位，分两种情况： 1.l,r的高位都取到了最大值，那么这一位必须能放1才可能有负贡献，l,r的低位都随便选。 2.l,r的高位相同且没有取到最大值，那么这一位必然能同时放1，l,r的低位还是随便选。

预处理一下n，就可以实现上述的操作。

#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int t,cas,bin[66]; LL n; const int mod=1e9+7; int mul(int x,int y){ return 1ll*x*y%mod; } int add(int x,int y){ x+=y; if(x>=y)x-=mod; if(x<0)x+=mod; return x; } int fac[66]; int nxt[66],pre[66]; int main() { ios::sync_with_stdio(false); fac[0]=1; for(int i=1;i<=60;i++)fac[i]=mul(fac[i-1],2); for(cin>>t,cas=1;cas<=t;cas++){ cin>>n;int now=0; for(LL x=n;x;x>>=1)bin[++now]=x%2; //从低到高 [1,now] for(int i=1;i<=now;i++)nxt[i]=add(nxt[i-1],mul(fac[i-1],bin[i])); pre[now+1]=0; for(int i=now;i>=1;i--)pre[i]=add(mul(2,pre[i+1]),bin[i]); int ans=0; for(int i=1;i<=now;i++){ if(bin[i]){ ans=add(ans,(nxt[i-1]+1));//高位为之前的最高位 pre[i+1] } ans=add(ans,mul(fac[i-1],pre[i+1]));//高位动 [0,pre[i+1]) } ans=mul(ans,(n+1)%mod); for(int i=1;i<=now;i++){ if(bin[i]){ ans=add(ans,-mul(nxt[i-1]+1,nxt[i-1]+1)); } ans=add(ans,-mul(mul(fac[i-1],fac[i-1]),pre[i+1])); } cout<<"Case #"<<cas<<": "<<ans<<'\n'; } return 0; }