题目
Binary Indexed Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 42 Accepted Submission(s): 7
Problem Description
Recently, Mr. Frog has learned binary indexed tree. Here is the code of adding t to the interval [1,x]:
If Mr. Frog is required to add t to the interval [l,r], he will add(r,t), and then add(l - 1,-t).
The cost of an interval [l,r] is defined as the number of the “really changed point”. The “really changed point” is the point whose value is modified by the given code.
For example, in order to add 1 to the interval [6,6], Mr. Frog will add 1 to the interval [1,6] (a[6] and a[4] will be added by 1), and add -1 to the interval [1,5] (a[5] and a[4] will be added by -1).
As the result, a[6] will be added by 1, a[5] will be added by -1, and a[4] will be added by 0. a[6] and a[5] are “really changed point”, and the cost is 2.
Mr. Frog wants to calculate the sum of the cost of the interval [l,r] ⊆ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.
void add (int x, int t ){
for (int i = x; i != 0; i -= i & (-i))
a[i] += t;
}
If Mr. Frog is required to add t to the interval [l,r], he will add(r,t), and then add(l - 1,-t).
The cost of an interval [l,r] is defined as the number of the “really changed point”. The “really changed point” is the point whose value is modified by the given code.
For example, in order to add 1 to the interval [6,6], Mr. Frog will add 1 to the interval [1,6] (a[6] and a[4] will be added by 1), and add -1 to the interval [1,5] (a[5] and a[4] will be added by -1).
As the result, a[6] will be added by 1, a[5] will be added by -1, and a[4] will be added by 0. a[6] and a[5] are “really changed point”, and the cost is 2.
Mr. Frog wants to calculate the sum of the cost of the interval [l,r] ⊆ [1,n] where l and r are two integers. Help Mr. Frog solve the problem.
Input
The first line contains only one integer T (
T≤10000), which indicates the number of test cases.
For each test case, it contains an integer n ( 1≤n≤1018).
For each test case, it contains an integer n ( 1≤n≤1018).
Output
For each test case, output one line ”Case #x: y”, where x is the case number (starting from 1), y is the sum of the cost (modulo 1000000007).
Sample Input
3 1 2 3
Sample Output
Case #1: 1 Case #2: 4 Case #3: 10
大意
分析之后题意就是，给出一个n，求由[0,n]中的数组成的所有二元组(x,y)其中x<y的cost值的和，这个cost的计算方法是，把x不断地减去二进制表示下的最末尾一个1，比如(10101->10100->10000->0)，把出现过的数放到集合S_x，y做相同处理形成集合S_y，cost就是两个集合中出现了1次的数的个数。
分析
用总和减去重复的，在不考虑重复的情况下，某个数的cost就是这个数二进制下1的个数，因为每个数会被用到n次，所以总共是n*(1到n的数中二进制下1的总和)，这个可以用数位dp的方法，f[i][j]表示长度为i的前面已经出现了j个1的数的个数。
重复部分的计算比较麻烦，注意到对于某个二元组，他们之间会产生的重复的对数是这两个数写成二进制，并向右对齐，前面补0(比如x=10010,y=110,写成x=10010,y=00110)，他们的cost是从左开始看完全重复的部分里1的个数，比如(
1010010和
1011010的cost是2)，然后设sg[i][j]表示长度为i的并且前面完全相同部分有j个1的
二元组的对数，这个数组可以直接用组合数算出来。
代码
#include<cstdio>
#include<cstring>
#define LL __int64
#define mod 1000000007
LL f[70][70],sg[70][70],mi[70],C[70][70];
int dig[70],len;
void init()
{
int i,j,k;
memset(f,0,sizeof(f));
memset(sg,0,sizeof(sg));
memset(mi,0,sizeof(mi));
for(i=0;i<=65;i++)
{
C[0][i]=0;
C[i][0]=1;
}
for(i=1;i<=65;i++)
for(j=1;j<=65;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
mi[0]=1;
for(i=1;i<=65;i++)
mi[i]=mi[i-1]*2%mod;
f[0][0]=1;
f[1][1]=1;
f[1][0]=1;
for(i=2;i<=65;i++)
{
for(j=0;j<=i;j++)
{
if(j-1>=0)
f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
f[i][j]=(f[i][j]+f[i-1][j])%mod;
}
}
for(i=1;i<=65;i++)
{
sg[i][0]=(sg[i][0]+2*mi[i-1]%mod*mi[i-1]%mod)%mod;
for(k=0;k<i-1;k++)
{
for(j=0;j<=k+1;j++)
{
sg[i][j]=(sg[i][j]+C[k+1][j]*2%mod*mi[i-k-2]%mod*mi[i-k-2]%mod)%mod;
}
}
}
}
LL cal1(LL n)
{
LL ans=0;
int i,j;
int cnt1=0;
for(i=len-1;i>=0;i--)
{
if(dig[i]==0)
continue;
for(j=i;j>=0;j--)
ans=(ans+f[i][j]*(j+cnt1)%mod)%mod;
cnt1++;
}
ans=(ans+cnt1)%mod;
n%=mod;
ans=ans*n%mod;
return ans;
}
LL cal2(LL n)
{
LL ans=0;
int i,j,k;
int cnt1=0;
for(i=len-1;i>=0;i--)
{
if(dig[i]==0)
continue;
n-=((LL)1<<i);
ans=(ans+(n+1)%mod*mi[i]%mod*cnt1*2%mod)%mod;
for(k=0;k<i;k++)
{
ans=(ans+sg[i][k]*(k+cnt1)%mod)%mod;
}
cnt1++;
}
return ans;
}
int main()
{
LL n;
int t,cas=1;
scanf("%d",&t);
init();
while(t--)
{
scanf("%I64d",&n);
len=0;
LL tmp=n;
while(tmp)
{
dig[len++]=tmp%2;
tmp/=2;
}
LL ans=cal1(n);
printf("Case #%d: %I64d\n",cas++,(ans-cal2(n)+mod)%mod);
}
return 0;
}