Hdu5921 Binary Indexed Tree
发布时间:2020-12-14 03:45:26 所属栏目:大数据 来源:网络整理
导读:Hdu5921 Binary Indexed Tree 思路 计数问题,题目重点在于二进制下1的次数的统计,很多题解用了数位DP来辅助计算,定义g(i)表示i的二进制中1的个数, $ans = sum_{i=1}^n sum_{j=0}^{i-1} g(i,j) = 0.5sum_{i=0}^nsum_{j=0}^n[g(i)+g(j)-2g(lcp(i,j))]
Hdu5921 Binary Indexed Tree 思路计数问题,题目重点在于二进制下1的次数的统计,很多题解用了数位DP来辅助计算,定义g(i)表示i的二进制中1的个数, $ans = sum_{i=1}^n sum_{j=0}^{i-1} g(i,j) = 0.5sum_{i=0}^nsum_{j=0}^n[g(i)+g(j)-2g(lcp(i,j))] $ 即先计算每个位的贡献,再减去重复的地方。 先计算前者,每个数会出现 同理,计算lcp的计数只需考虑两个数同时满足的情况即可。 代码#include<bits/stdc++.h> using namespace std; const int N = 65; typedef long long ll; const ll mod = 1e9+7LL; int a[N]; ll l[N],r[N],e[N]; ll get(int x){ ll cnt = 0LL; for(int i=0;i<x;i++) cnt += a[i]; for(int i=x-1;i>=0;i--){ if(a[i]){ if(i) cnt += r[i-1]; } { cnt += l[i+1]*e[i]%mod; cnt %= mod; } } return cnt; } ll getlcp(int x){ ll cnt = 0LL; for(int i=x-1;i>=0;i--){ if(a[i]){ if(i) (cnt += (r[i-1]+1)*(r[i-1]+1)%mod)%=mod; else{ (cnt += 1LL)%=mod; } //printf("cnt %lldn",cnt); } { cnt += l[i+1]*e[i]%mod*e[i]%mod; cnt %= mod; //printf("cnt %lldn",cnt); } } //printf("cnt %lldn",cnt); return cnt; } int main(){ int i,T,len,t; ll n,m,ans; scanf("%d",&t); T=0; for(int i=0;i<63;i++) e[i]=(1LL<<i)%mod; while(t--){ scanf("%lld",&n); m=n; len=0; for(;m;m>>=1) a[len++]=m%2; l[len]=0; r[0]=a[0]; for(i=1;i<len;i++) r[i]=(r[i-1]+a[i]*(1LL<<i)%mod)%mod; for(i=len-1;i>=0;i--) l[i] = ((l[i+1]<<1LL) + a[i])%mod; ans = ((n+1)%mod*get(len))%mod; //printf("%lldn",ans); ans -= getlcp(len); ans = (ans%mod+mod)%mod; printf("Case #%d: %lldn",++T,ans); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |