http://acm.hdu.edu.cn/showproblem.php?pid=6304
题意
给出一个数列的定义，a[1]=a[2]=1,a[n]=a[n-a[n-1]]+a[n-1-a[n-2]](n>=3)。求前n项和，n<=1e18。
分析
一看就是得打表找规律或推公式的题目。
先把a[i]打出来： 1 1 2 2 3 4 4 4 5 6 6...
乍眼一看每个数字出现的次数有点意思，于是打出每个数出现次数：
数值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
次数 2 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5
感觉第一个1很不和谐啊，先忽略这个1看看：
数值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
次数 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5
可以看到前2^i个数的出现次数是由前2^(i-1)个数复制两次，并把2^i的次数+1得到的。
这样就得到数值出现次数的规律了，设cnt[i]为前2^i个数的次数之和，那么cnt[i]=2*cnt[i-1]+1。
有了cnt[i]，对于一个下标n，可以求出a[n]的值，相反也可以求出值为a[n]的第一个位置。
然后怎么求前n项和呢？把相同出现次数的值输出看看：
1-- 1,3,5,7,9....
2-- 2,6,10,14...
3-- 4,12,20,28...
4-- 8,24,40,56...
....
很明显的规律，对于次数k，对应数值形成一个首项为2^(k-1)，公差为2^k的等差数列。这个等差数列的每个值都出现k次。
所以，可以枚举次数，计算以a[n]为上界的项数，再把这个等差数列的和*次数加到答案中。
需要注意，计算等差数列时不能把a[n]算进去，因为a[n]出现的次数在n的限制下是不完全的，需要另外计算，这时就用到上面计算的a[n]出现的第一个位置了，由此算出a[n]实际出现的次数，再加到答案中。
由于数据是ll级别，出现相乘时不要忘记先模一下。
其它细节看代码。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll cnt[64],p[64]; //预处理2^i和cnt[i] void init(){ cnt[0]=p[0]=1; for(int i=1;i<=62;i++) cnt[i]=2*cnt[i-1]+1,p[i]=2*p[i-1]; } //计算a[n]的数值 ll caln(ll n){ if(n==1) return 1;//特殊处理 n--;//由于规律从实际的第二个开始计算 ll an = 0; for(int i=62;i>=0;i--){ while(cnt[i]<=n){ n-=cnt[i]; an+=p[i]; } } return an; } //根据a[n]计算最早出现的位置 ll gps(ll an){ if(an==1) return 1; an--; //同上 ll pos=0; for(int i=62;i>=0;i--){ while(p[i]<=an){ an-=p[i]; pos+=cnt[i]; } } return pos+1; } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int T; ll n; scanf("%d",&T); init(); ll _inv = 500000004;//2的逆元 while(T--){ scanf("%lld",&n); ll an = caln(n); ll cnt = n - gps(an);//a[n]出现的实际次数 ll ans = 0; for(int i=1;p[i-1]<=an;i++){//枚举次数，终结条件为某个等差数列的首项大于a[n] ll x1 = p[i-1]; //首项 ll d = p[i]; //公差 //项数。注意，正常的项数应该是((an-x1)/d+1)，但这里不能保证a[n]全部出现了， //所以当((an-x1)%d==0)时说明a[n]位于当前的等差数列中，需要根据实际个数来计算，于是不+1 ll num = ((an-x1)%d==0)?((an-x1)/d):((an-x1)/d+1); ll xn = x1 + (num-1)*d; //尾项 ll sum = (x1%mod+xn%mod)%mod*(num%mod)%mod*_inv%mod; //等差数列前num项和 ans = (ans+i*sum%mod)%mod; //加入答案，共出现i次 if((an-x1)%d==0) ans=(ans+cnt*(an%mod)%mod)%mod; //a[n]位于此数列，特别计算一下。 } printf("%lld ",ans+1);//由于计算中忽略了第一项1，最后加上 } return 0; }