[HDU6304][数学] Chiaki Sequence Revisited
-杭电多校2018第一场G
题目描述
现在抛给你一个数列(A)
现在需要你计算它的前缀和 (sumlimits_{i=1}^{n}a_i mod (10^9+7))
数据范围 (n(1le nle 10^{18}))
题目分析
不可描述的做法
拿到题目第一步对序列(A)打一个100的表，对吧，然后 "OEIS" 一下，发现真的有
(a[1..] = {1,2,2,3,4,4,4,5,6,6,7,8,8,8,8,9,....})
结果发现并没有什么用，既没有通项公式，更别说求和公式了。
大概正确的规律
可以发现每种数字的出现次数是由规律可循的，(1)出现了(1)次，(2)出现了(2)次，(3)出现了(1)次
我们设(f(x))代表数字(x)出现的次数
那么 (f[1..] = {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,....})
通过观察100项的表可以的出一个大概正确的规律，数字(x)会出现(1+log_2lowbit(x))次
至于(lowbit(x)) 是啥，可以去了解一下树状数组，表示 (min{2^k:2^k|x})
经过总结规律可以发现递推式，那么有
也就是 http://oeis.org/A001511 中提到的数列，但是知道出现次数并没有什么用，我们需要计算的是(f(x))
的前缀和，这样我们就可以知道(n)位置上表示的数字的值，即(a_n)的值。
我们设 $g(n) = sum^{n}_{i=1}f(i) $ ，可以简单推导一下
也就是说我们现在可以在(O(log N))时间计算出(g(n)) ，由于该函数显然是单调的，那么我们现在可以通过二分求得(a_n)对应的值，即 (a_n = min{k | g(k)ge n})。
然而题目要我们求前缀和，那么问题来了，我们现在计算单个值就需要(O(log^2N ))时间
如何计算出前缀和呢？考虑通过每个数字的出现次数入手。
由于每一行都相当于一个等差数列，现在的目标就是找到每一行的末项就好了。
也就是找到__最后一个小于(a_n)的值__，再用等差数列求和公式(O(1))计算出每一行的值，最后所有行加起来就是答案的主要部分了。
会发现经过上面的计算所有等于(a_n)的项没有计算入答案，我们只要计算出等于(a_n)的有多少项，最后再累加到答案，这道题就做完了。容易得到 (a_n)需要计算(n-g(a_n-1))次。根据最开始我对数列的偏移，正确的答案还需要再+1。整体复杂度为(O(log^2N+logN))
注:计算(a_n)需要 (O(log^2N))时间，需要估计二分上下界，否则会超时。
无比准确的题解
以下是多校官方给的题解。
考虑这个数列的差分数列，除了个别项，本质就是：(1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0,...)。
可以观测到，这个序列可以这么生成：一开始只有一个(1)，(1)变成(110)，(0)保持不变。迭代无穷多次后就是这个差分序列。
知道差分序列，可以应用阿贝尔变换，把(a)的前缀和搞成差分序列相关。不妨令差分序列是(da)，那么(a)的前缀和$$s(n)=(n-1)sum_{i=0}^{n-2}da(i) - sum_{i=0}^{n-2}da(i)i + 1$$。
利用(da)的分形结构，很容易算出(s(n))。
代码Code
/*
[HDU6304][数学]
Chiaki Sequence Revisited
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int inv2 = 500000004;
int T;
LL n;
LL calc(LL n) {
if(n<=1) return n;
else return calc(n/2)+n;
}
void solve() {
LL l=n/2-30,r=n/2+30,m,p=-1;
//需要预先估计上下界减少二分次数,否则会TLE.
while(l<=r) {
m = (l+r)/2;
if(calc(m)>n) r=m-1;
else l=m+1,p=m;
}
LL rest = ((n - calc(p))%MOD+MOD)%MOD;
LL ans = 0, s, t, e, k, c=1, x, y;
for(LL i=1;; i<<=1,c++) {
if(i>p) break;
x = i%MOD;
y = 2*i%MOD;
s = x;
k = ((p-i)/(2*i)+1)%MOD;
e = (y*(k-1)%MOD+i)%MOD;
ans = (ans+c*(s+e)%MOD*k%MOD*inv2%MOD)%MOD;
}
ans = (ans + rest*((p+1)%MOD)%MOD)%MOD;
printf("%lld
",ans+1);
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%lld",&n);
n--; //偏移一项
solve();
}
return 0;
}