Zq's Blog 算法,计数 [计数]hdu5921:Binary Indexed Tree

[计数]hdu5921:Binary Indexed Tree

题目大意

给定代码

    void add (int x, int t ){
        for (int i = x; i != 0; i -= i & (-i))
            a[i] += t;
    }

当你要给$[l,r]$区间加$x$时,肯定是先给$[1,l−1]$加$−x$,然后给$[1,r]$加$x$;

定义$f(l,r)$为在$a$数组为$0$时给区间$[l,r]$加$1$后,$a$数组有多少位置不为$0$;

给定$n$,求
$$
\sum_{l=1}^n\sum_{r=l}^nf(l,r)\ mod\ (10^9+7)
$$

题解

定义$g(i)$表示$i$在二进制下$1$的个数,$lcp(l,r)$表示$l,r$二进制的$lcp$的值(右对齐);

首先我们有
$$
\sum_{l=1}^n\sum_{r=l}^nf(l,r)\\
=\sum_{l=1}^n\sum_{r=l}^ng(l)+g(r)-2g(lcp(l,r))\\
=\frac{1}{2}\sum_{l=0}^n\sum_{r=0}^ng(l)+g(r)-2g(lcp(l,r))\\
=(n+1)\sum_{i=0}^ng(i)-\sum_{i=0}^n\sum_{j=0}^ng(lcp(i,j))\\
$$

对于第一部分$\sum_{i=0}^ng(i)$;

我们统计每一位的贡献即为$div[i-1]*2^{l-i}$,这里$i$为当前位(从1开始),$l$为当前长度,$div[i]$表示前$i$位的值,如$(10110)_2$,$div[3]=(101)_2=5$;

上式含义为如果这一位取$1$,前面可以取$0$~$div[i-1]-1$,后面可以取$0$~$2^{l-i}-1$;

如果第$i$位是$1$,则存在$i$前面为$div[i-1]$的状况,这种状态在上面没有被统计到,所以答案还要加上$tot[i+1]+1$,$tot[i]$表示后$i$位的值,如$(10110)_2$,$tot[3]=(110)_2=6$;

不要忘了乘上$n+1$;

对于第二部分$\sum_{i=0}^n\sum_{j=0}^ng(lcp(i,j))$;

和上面类似,统计第$i$位的贡献为$div[i-1]*2^{l-i}*2^{l-i}$;如果为第$i$位则还有$(tot[i+1]+1)^2$;注意这里是减;

这样总时间复杂度为$O(Tlogn)$;

#include<cstdio>
#include<algorithm>
#define tt 1000000007
using namespace std;
typedef long long ll;
inline void write(ll x){int num[100]={0};num[0]+=!x;while (x) num[++num[0]]=x%10,x/=10;for (int i=num[0];i;i--) putchar(num[i]+'0');puts("");}
inline ll read(){
    ll Res=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&ch<='9') Res=Res*10ll+ch-'0',ch=getchar();
    return Res;
}
ll N,M,Ans;
int Bin[105],len;
ll tot[105],Div[105],Pow[105]={1};
int main()
{
    for (int i=1;i<63;i++) Pow[i]=(Pow[i-1]<<1)%tt;
    for (int T=read(),t=1;t<=T;t++){
        N=read();M=N;len=tot[0]=0;Ans=0;
        while (M) Bin[++len]=M%2,M>>=1;tot[len+1]=0;
        for (int l=1,r=len;l<=r;l++,r--) swap(Bin[l],Bin[r]);
        for (int i=1;i<=len;i++) Div[i]=((Div[i-1]<<1)+Bin[i])%tt;
        for (int i=len;i;i--) tot[i]=(tot[i+1]+Pow[len-i]*Bin[i])%tt;
        for (int i=1;i<=len;i++){
            if (Bin[i]) (Ans+=tot[i+1]+1)%=tt; //前面相同,第i位为1,后面可以取tot[i-1]+1种 
            (Ans+=Div[i-1]*Pow[len-i]%tt)%=tt; //把这一位看成0,前面有Div[i+1]种,第i位为1,后面任取 
        }
        (Ans*=(N+1)%tt)%=tt;
        for (int i=1;i<=len;i++){
            if (Bin[i]) (Ans+=tt-(tot[i+1]+1)*(tot[i+1]+1)%tt)%=tt; //同理 
            (Ans+=tt-Div[i-1]*Pow[len-i]%tt*Pow[len-i]%tt)%=tt;
        }
        printf("Case #%d: ",t);write(Ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注