HDOJ6304

发表于 | 分类于

题目链接：HDOJ6304

题意：根据数列递推给了你这么一个式子，求前n项和mod 1e9+7

题目分析

递推很复杂，下标含有项，一般来说是求不出通项的，所以$O(1)$的算法应该是没有的，数据范围又很大 n最大1e18 时限1000 分析一下 $O(n)$、$O(\sqrt n)$啥的大概是不行的 对数级别的可以考虑一下

初级打表

一开始拿到题目毫无头绪 打表看一下$a_n$前几项有没有规律
前100项：

a_1 = 1
a_2 = 1
a_3 = 2
a_4 = 2
a_5 = 3
a_6 = 4
a_7 = 4
a_8 = 4
a_9 = 5
a_10 = 6
a_11 = 6
a_12 = 7
a_13 = 8
a_14 = 8
a_15 = 8
a_16 = 8
a_17 = 9
a_18 = 10
a_19 = 10
a_20 = 11
a_21 = 12
a_22 = 12
a_23 = 12
a_24 = 13
a_25 = 14
a_26 = 14
a_27 = 15
a_28 = 16
a_29 = 16
a_30 = 16
a_31 = 16
a_32 = 16
a_33 = 17
a_34 = 18
a_35 = 18
a_36 = 19
a_37 = 20
a_38 = 20
a_39 = 20
a_40 = 21
a_41 = 22
a_42 = 22
a_43 = 23
a_44 = 24
a_45 = 24
a_46 = 24
a_47 = 24
a_48 = 25
a_49 = 26
a_50 = 26
a_51 = 27
a_52 = 28
a_53 = 28
a_54 = 28
a_55 = 29
a_56 = 30
a_57 = 30
a_58 = 31
a_59 = 32
a_60 = 32
a_61 = 32
a_62 = 32
a_63 = 32
a_64 = 32
a_65 = 33
a_66 = 34
a_67 = 34
a_68 = 35
a_69 = 36
a_70 = 36
a_71 = 36
a_72 = 37
a_73 = 38
a_74 = 38
a_75 = 39
a_76 = 40
a_77 = 40
a_78 = 40
a_79 = 40
a_80 = 41
a_81 = 42
a_82 = 42
a_83 = 43
a_84 = 44
a_85 = 44
a_86 = 44
a_87 = 45
a_88 = 46
a_89 = 46
a_90 = 47
a_91 = 48
a_92 = 48
a_93 = 48
a_94 = 48
a_95 = 48
a_96 = 49
a_97 = 50
a_98 = 50
a_99 = 51
a_100 = 52


好像没什么规律

高级打表

不过我们好像注意到总是连续的几个值一起出现
那我们统计一下每一个值出现的次数
表：

value: 1 times: 2
value: 2 times: 2
value: 3 times: 1
value: 4 times: 3
value: 5 times: 1
value: 6 times: 2
value: 7 times: 1
value: 8 times: 4
value: 9 times: 1
value: 10 times: 2
value: 11 times: 1
value: 12 times: 3
value: 13 times: 1
value: 14 times: 2
value: 15 times: 1
value: 16 times: 5
value: 17 times: 1
value: 18 times: 2
value: 19 times: 1
value: 20 times: 3
value: 21 times: 1
value: 22 times: 2
value: 23 times: 1
value: 24 times: 4
value: 25 times: 1
value: 26 times: 2
value: 27 times: 1
value: 28 times: 3
value: 29 times: 1
value: 30 times: 2
value: 31 times: 1
value: 32 times: 6
value: 33 times: 1
value: 34 times: 2
value: 35 times: 1
value: 36 times: 3
value: 37 times: 1
value: 38 times: 2
value: 39 times: 1
value: 40 times: 4
value: 41 times: 1
value: 42 times: 2
value: 43 times: 1
value: 44 times: 3
value: 45 times: 1
value: 46 times: 2
value: 47 times: 1
value: 48 times: 5
value: 49 times: 1
value: 50 times: 2


看一下这个times表 可以发现奇数出现的次数为1（不要管那个1 因为那是首项限制了）
出现2次的数是2 6 10 14 …
出现3次的数是 4 12 20 28 …
出现4次的数是 8 24 40 56 …
…
出现i次的数是$2^{i-1}$ (1 3 5 7 9 …)
观察一下这些数的二进制表达
可以发现 i 这个数一共出现了__builtin_ctz(i)+1次
或者说 出现了$log_2{lowbit(i)}+1$次
没错 这个lowbit就是那个树状数组的lowbit

算法分析

我们先把$a_1$剔除掉 因为这个首项存在有点碍事 之后再加回来就行了
那么数列所有项往前面移一个下标 所询问的n也相应的要-1
便于叙述 我们记 $f(x)=log_2{lowbit(i)}+1$
根据之间打的$a_i$值表 我们要求的$a_n$之前应该有许多个一块一块值一样的项
$a_n$周围应该有一些（也有可能没有）和它值一样的项
由于我们是求$a_i$的前n项和 那我们把$a_n$之前项一块一块一起算（反正值一样，出现次数也可以计算）
那么首先我们有一个问题——$a_n$的值是多少

问题1：$a_n$的值

便于叙述 我们记$sum(x)=\sum_{i=1}^x{f(i)}$表示值为1~x一共有多少项

如果我们朴素的找 应该是从头开始往后扫n个 这样太慢 我们直接算
找一个最大的t使得：
$\sum_{k=1}^{t}f(k)\le n$
那么 $a_n$的值分两种情况

  1. $\sum_{k=1}^{t}f(k) = n$ 这个时候 $a_n=t$ （$a_n$正好位于值为$t$的那一堆数的最后一个）
  2. $\sum_{k=1}^{t}f(k) < n$ 这个时候 $a_n=t+1$ （$a_n$位于值为$t+1$那一堆数中）

然后我们要开始计算$a_n$之前数的和

问题2：前一部分和

便于叙述 我们记$psum(x)=\sum_{i=1}^x{i\cdot f(i)}$表示值为1~x的所有项和
由于有可能一个值相同的块被$a_n$切开（只有$a_n$之前的项对答案有贡献，后面的没有）
那么我们先计算$a_n$之前的完整块的和，所谓前一部分和
前一部分和为$psum(t)$

问题3：后一部分和

后一部分和就是与$a_n$处在同一块下对答案有贡献的项总和
当然如果正好是问题1的情况1

  1. $\sum_{k=1}^{t}f(k) = n$ 这个时候 $a_n=t$ （$a_n$正好位于值为$t$的那一堆数的最后一个）

那么后一部分和是没有的。。因为并没有哪一个块被$a_n$所“切开”

问题4：总和

由以上叙述 总和

  1. $ans=psum(t),when \sum_{k=1}^{t}f(k) = n$
  2. $ans=psum(t)+(t+1)\cdot (n-sum(t)),when \sum_{k=1}^{t}f(k) < n$

优化1

找$t$
由于和式满足二分条件（递增）
那我们直接二分查找这个$t$
复杂度$O(\log n)$

优化2

我们会发现 $sum(i)$ 算起来很慢 如果乱搞的话是 $O(n)$ 的 前面已经说过了这样的复杂度不行
观察一下 $f(x)$ 的定义
它计算了数i在二进制下末尾0的个数
那我们换一种sum(x)的表示法
我们可以先固定二进制位下k-1个末尾0 并固定第k位为1
其他位随意组合 但最终值不能超过x
那么这样就统计了所有f(x)=k的和
表示为 $\lfloor \frac{x}{2^k} \rfloor$
$k$从1枚举到最大 那么
$sum(x)=\sum_{k=1}^{MAX}\lfloor \frac{x}{2^k} \rfloor$
复杂度是$O(\log n)$

优化3

同样的$psum(x)$算起来也很慢 乱搞也是$O(n)$的
上面我们说过一个规律

出现i次的数是$2^{i-1}$ (1 3 5 7 9 …)

1 3 5 7 9 … 是等差数列 和可以用$O(1)$公式法搞定
那么重新叙述$psum(x)$ 我们可以先把出现1次的数全部加起来 然后把出现2次的 出现3次的 出现4次的数都加起来 由于出现i次的数最小是$2^{i-1}$嘛 那么这边求和也是$O(\log n)$的
问题是等差数列的末项是啥
假设出现i次的数的最后一个数是$2^{i-1}*(2p-1)$其中$p\in N^+$那么这个数满足

  1. $p$最大
  2. $2^{i-1}*(2p-1)\le x$

这个还是挺方便解的 移项完了是 $p \le \frac{\frac{x}{2^{i-1}}+1}{2}$ 那$p$直接取$\lfloor\frac{\lfloor\frac{x}{2^{i-1}}\rfloor+1}{2}\rfloor$就行了
然后求一波等差数列和 (首项+尾项)*(项数))/2
$S=2^{i-1}\cdot p\cdot p$
完了我们回去算 $psum(x)=\sum_{i=1}^{MAX}{i\cdot 2^{i-1}\cdot p\cdot p}$
复杂度$O(\log n)$

注意

我们一开始剔掉了$a_1$ 不要忘了把它加回来

复杂度

答案表达式是这样的：

  1. $ans=psum(t),when \sum_{k=1}^{t}f(k) = n$
  2. $ans=psum(t)+(t+1)\cdot (n-sum(t)),when \sum_{k=1}^{t}f(k) < n$

在情况1下 就是$psum(x)$的复杂度$O(\log n)$
在情况2下 复杂度是$O(\log n\cdot\log n)$
所以总的复杂度是 $O(\log n\cdot \log n)$
结合一下数据规模 嗯 应该不会炸了…
ps:由于这题的时限卡的有点紧（标程好像是用阿贝尔变换做的）多校现场赛有人用$O(\log n\cdot \log n)$ 的算法T了 所以最好在写的时候注意下常数优化

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD=1e9+7;

ll pm[100];//power of 2

inline ll psum(ll x){
    ll ret=0;
    for(int i=1;pm[i-1]<=x;i++){
        ll tmp=(x>>(i-1))+1;
        tmp>>=1;
        tmp%=MOD;
        ret+=i%MOD*(pm[i-1]%MOD)%MOD*tmp%MOD*tmp%MOD;
        ret%=MOD;
    }
    return ret;
}

inline ll sum(ll x){
    ll ret=0;
    for(int i=0;pm[i]<=x;i++){
        ret+=(x>>i);
    }
    return ret;
}

inline bool check(ll t,ll n){
    ll v=sum(t);
    return v<=n;
}

inline ll find_t(ll n){
    ll l=1,r=n;
    ll ret=-1;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid,n)){
            l=mid+1;
            ret=mid;
        }
        else r=mid-1;
    }
    assert(ret!=-1);
    return ret;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // int begin_time=clock();
    #ifndef ONLINE_JUDGE
    freopen("input.in","r",stdin);
    freopen("output.o","w+",stdout);
    #endif
    pm[0]=1;
    for(int i=1;i<=61;i++){
        pm[i]=pm[i-1]<<1;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        ll n;
        scanf("%lld",&n);
        if(n==1){
            puts("1");
            continue;
        }
        else if(n==2){
            puts("2");
            continue;
        }
        n--;
        ll t=find_t(n);
        ll ans=psum(t)%MOD;
        ll v_sum=sum(t);
        if(n>v_sum){
            ans+=(n-v_sum)%MOD*(t+1)%MOD;
            ans%=MOD;
        }
        ans=(ans+1)%MOD;
        printf("%lld\n",ans);
    }
    // cout<<"time use: "<<clock()-begin_time<<" ms"<<endl;
    return 0;
}