【计数】hdu5921Binary Indexed Tree

二进制拆位计算贡献

题目描述

树状数组是一种常用的数据结构，下面是树状数组用于给区间 [1,x] 内的数加 t 的代码：

1 void add(int x,int t){
2     for (int i=x;i;i-=(i&(-i))){
3         cnt[i]+=t;
4     }
5 }

当你要给 $[l, r]$

令 $f (l, r)$

现在给定 $n$ sum_{l=1}^{n} sum_{r=1}^{n} f(l,r)，对1e9+7取模

输入格式

第一行 $T$

$T$ $T$ $T$

输出格式

$T$

数据范围

$100 %$

题目分析

这题主流做法是数位dp。不过从hdu5921Binary Indexed Tree学习到一种拆位算贡献的方法

（但是请注意！上面引用的这篇博客关于f(i),g(i)的分析有写错的地方！）

本题树状数组求的是后缀和；而∑f(l,r)求的是l-1和r这两个数在依次减去lowbit的过程中不同的数的个数：那么只有当l-1和r变成lcp(l-1,r)时，接下去的数才会相同。

记g(i)为i二进制中1的个数，所求即

（公式崩了只能用图片）

经过上面分析之后，问题相当于转变为求∑g(i)和Σg(lcp(l-1,r))。由于数据范围是10^18级别，显然我们需要log算法。

将n二进制拆位，考虑从右往左第$i$位的贡献。记[i+1...lens]在十进制下为nxt[i+1]，[1...i-1]在十进制下为pre[i-1]。

1.计算gi第一步：左边的数不改变

那么为了不大于原数，右边的数应取0...pre[i-1]。

当ai==1时，有pre[i-1]+1的贡献

2.计算gi第二步：左边的数可改变

与上一种情况相对应，左边的数应取0...nxt[i+1]-1.那么此时右边的数可以任意取值，有2^i种取值。

所以这种情况下，无论ai取值如何，都有nxt[i+1]*2^i的贡献。

至于还要处理两两lcp的部分，则与之类似。由于是数对之间的负贡献，算的时候再多乘上去就好了。

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 const ll MO = 1000000007;
 4 
 5 int T,bin[103],lens;
 6 ll n,ans,power[103],pre[103],nxt[103];
 7 
 8 ll read()
 9 {
10     char ch = getchar();
11     ll num = 0;
12     bool fl = 0;
13     for (; !isdigit(ch); ch=getchar())
14         if (ch=='-') fl = 1;
15     for (; isdigit(ch); ch=getchar())
16         num = (num<<1)+(num<<3)+ch-48;
17     if (fl) num = -num;
18     return num;
19 }
20 int main()
21 {
22     T = read(), power[0] = 1;
23     for (int i=1; i<=60; i++) power[i] = (power[i-1]<<1)%MO;
24     while (T--)
25     {
26         n = read(), ans = lens = 0;
27         for (ll x=n; x; x>>=1) bin[++lens] = x&1;
28         pre[0] = nxt[lens+1] = 0;
29         for (int i=1; i<=lens; i++) pre[i] = (pre[i-1]+power[i-1]*bin[i])%MO;
30         for (int i=lens; i>=1; i--) nxt[i] = ((nxt[i+1]<<1)+bin[i])%MO;
31         for (int i=1; i<=lens; i++)
32         {
33             if (bin[i]) pre[i-1]++, ans = (ans+pre[i-1])%MO;
34             ans = (ans+nxt[i+1]*power[i-1]%MO)%MO;
35         }
36         ans = (n+1ll)%MO*ans%MO;
37         for (int i=1; i<=lens; i++)
38         {
39             if (bin[i]) ans = (ans+MO-pre[i-1]*pre[i-1]%MO)%MO;
40             ans = (ans-nxt[i+1]*power[i-1]%MO*power[i-1]%MO+MO)%MO;
41         }
42         printf("%lld
",ans);
43     }
44     return 0;
45 }

END