推了好久。。。
这个题肯定是先把an打出来。。1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9
发现从小到大出现，而且除了1，出现次数为二进制形式最低位的位数。。
然后是求和。。既然和二进制有关，优先考虑n=2^k的情况。。发现an都是n/2。。然后就要考虑前n/2怎么推出n了。。
1 2 2 3 4 4 4
5 6 6 7 8 8 8
贴一下 2-8和9-15（因为第一项不符合最低位的规律）可以发现他们都只差了4，由a[n/2]和a[n]的关系可以推出差值为a[n]-a[n/2]=n/4
然后就可以yy公式了。。设s为前缀和。。
s[n]={s[n/2]}+{(s[n/2]-1)+(n/2-1)*(n/4)}+{n/2}
其中第一项为前n/2的和；第二项为n+1~n-1的和，可以在2~n/2的基础上+项数*n/4得到；第三项就是n/4了。。
这样就解决了s[2^k]了。。
然后其他的呢？其实可以先把n表示成二进制。。然后设最高位为m
前2^m可以先算出来，剩下的减去a[2^m]，可以发现会变成从2开始的a序列。。（和算2^k的思想类似）然后补上一个1就变成了另一个s。。
这样按位减可以依次得到答案了。。
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━━━━━━━━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-12
#define succ(x) (1LL<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 10000005
#define nm 2000005
#define N 1000005
#define M(x,y) x=max(x,y)
const double pi=acos(-1);
const ll inf=1e9+7;
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll n,c[NM],ans,d[NM];
int main(){
c[1]=2;c[0]=1;
inc(i,2,63)c[i]=(c[i-1]*2%inf+((succ(i-2)%inf)*((succ(i-1)+1)%inf))%inf-1)%inf;
d[0]=1;d[1]=1;inc(i,2,63)d[i]=succ(i-1)%inf;
//inc(i,1,6)printf("%d\n",c[i]);
int _=read();while(_--){
n=read();ans=0;
if(n==1){printf("1\n");continue;}
while(n>1){
int i=log(n*1.0)/log(2.0);
ans+=c[i]%inf;
ans%=inf;
n-=succ(i);
if(!n)break;
ans+=n%inf*d[i]%inf;ans%=inf;
n++;ans--;ans=(ans+inf)%inf;
}
if(n==1)ans++;
printf("%lld\n",(ans+inf)%inf);
}
return 0;
}
Chiaki Sequence Revisited
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 887 Accepted Submission(s): 203
Problem Description
Chiaki is interested in an infinite sequence a1,a2,a3,..., which is defined as follows:
an={1an−an−1+an−1−an−2n=1,2n≥3
Chiaki would like to know the sum of the first n terms of the sequence, i.e. ∑i=1nai. As this number may be very large, Chiaki is only interested in its remainder modulo (109+7).
Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤105), indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤1018).
Output
For each test case, output an integer denoting the answer.
Sample Input
10 1 2 3 4 5 6 7 8 9 10
Sample Output
1 2 4 6 9 13 17 21 26 32
Source
2018 Multi-University Training Contest 1
Recommend
liuyiding
Statistic | Submit | Discuss | Note