[HDU6304]Chiaki Sequence Revisited

Description
Chiaki is interested in an infinite sequence (a_1,a_2,a_3,...) which is defined as follows:

[a_n=egin{cases} 1 &,n=1,2\a_{n−a_{n−1}}+a_{n−1−a_{n−2}}&,ngeqslant3end{cases} ]

Chiaki would like to know the sum of the first (n) terms of the sequence, i.e. (sumlimits_{i=1}^na_i). As this number may be very large, Chiaki is only interested in its remainder modulo ((10^9+7)).

Input
There are multiple test cases. The first line of input contains an integer (T (1leqslant Tleqslant 10^5)), indicating the number of test cases. For each test case:
The first line contains an integer (n (1leqslant nleqslant 10^{18})).

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

---

遇到看不懂的数列，首先就应该根据它的构造方法打表找规律

通过打表可得数列前几项为1,1,2,2,3,4,4,4,5,6,6,7,8,8,8,8,...容易发现，在除去最开始的1后，记(c_i)为(i)出现的次数，则有(c_{2k}=c_k+1,c_{2k+1}=1)

我们记(s_k=sumlimits_{i=1}^kc_i)，则有

(s_{2k}=(c_1+c_3+....+c_{2k-1})+(c_2+c_4+...+c_{2k})=s_k+2k)

(s_{2k+1}=s_{2k}+c_{2k+1}=s_k+2k+1)

故可得(s_n)的递推式(s_n=s_{lfloorfrac{n}{2} floor}+n)，此时(s_n)表示1~n在序列中总共出现的次数

题目要求(S=sumlimits_{i=1}^na_i)，我们结合打表的数据，对其进行分组可得(S=sumlimits_{i=1}^n{i}+sumlimits_{i=1}^{lfloorfrac{n}{2} floor}2 imes i+sumlimits_{i=1}^{lfloorfrac{n}{2^2} floor}2^2 imes i+...=sumlimits_{j=0}sumlimits_{i=1}^{lfloorfrac{n}{2^j} floor}2^j imes i)

故我们可用二分，通过(s_n)找到一个合适的(n)，再根据上式计算(S)，最后再加上一些多出来的部分即可

并且，根据打表得出的规律，我们可以发现(n)基本在(frac{N}{2})附近波动（(N)为读入），故可以缩小二分的范围

/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline T frd(T x){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
template<typename T>inline T read(T x){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int P=1e9+7,Inv=5e8+4;
ll Cnt(ll x){return !x?0:Cnt(x>>1)+x;}
ll Binary_Search(ll l,ll r,ll m){
	while (l<=r){
		ll mid=(l+r)>>1;
		if (Cnt(mid)>m)	r=mid-1;
		else	l=mid+1;
	}
	return l-1;
}
int main(){
	int T=read(0);
	while (T--){
		int Ans=1;
		ll m=read(0ll)-1,n=Binary_Search((m>>1)-100,(m>>1)+100,m);
		for (int i=0;1ll<<i<=n;i++){
			ll delta=1ll<<i,E=n/delta*delta;
			Ans=(Ans+1ll*(E%P)*((E/delta+1)%P)*Inv%P)%P;
		}
		Ans=(Ans+1ll*(m-Cnt(n))%P*((n+1)%P)%P)%P;
		printf("%d
",Ans);
	}
	return 0;
}