补题 18年 杭电多校第一场 Chiaki Sequence Revisited
推荐博客：https://blog.csdn.net/ac_hunter/article/details/81194766
1.找出每个数字出现次数的规律 数字X的出现次数为 log2（lowbit（x）） + 1.
2.找出相同出现次数的数字的规律
1） 1 3 5 7 9....... 出现一次
2） 2 6 10 14..... 出现两次
... 等差数列
求前n项和， 由于 数字a[n] 可能没有完全在前n项里 所以我们要找到最后一个完全出现在前n项里的数字。
怎么找？
设我们要找的数字为X 那么出现
一次的数字有 1 3 5..... (1 到 X 之间的奇数 共 [ (X + 1) / 2 ] 个
两次的数字有 2 6 10.... （1 到 [X/2] 的奇数的两倍 数量就用[X/2]带入到上式的X中）
同理三次的有 4 12 20 28 （1 到 [x/4]的奇数的四倍）
这么多数字加起来的个数就是最后X的下标 （引用https://blog.csdn.net/ac_hunter/article/details/81194766中的一段话）
引用：
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
证明过程 ：
那么我们现在就需要算出前 n0 项的和 再加上缺少了的 n - n0 个 （X + 1）
对于每个由出现 i 次的数字构成的等差数列的和为 i * 2的i次方*数字个数的平方 数字个数Xi = [([X/(2^(i-1))]+1)/2]
然后就可以算了 计算过程中要记得及时取模。
最后AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll chen(ll a, ll b, ll c) // 计算乘积并取模
{
a %= mod, b %= mod, c %= mod;
return (((a*b)%mod)*c)%mod;
}
ll cntnum(ll x) // 计算 使x完全出现需要多少项
{
ll ans = 1, i = 1; // 数列中 1 出现两次 按照规律我们只计算 1 出现一次 所以要多加1个
while(x)
{
ans += i * 1ll * ((x + 1) >> 1); //计算出现 i 次的数列
i++, x >>= 1;
}
return ans;
}
ll findx(ll n)
{
ll l = max(((n + 1) >> 1) - 100, 1ll*1), r = 100 + (n + 1) >> 1, mid; // 二分查找 在 n/2-100， n/2+100 之间查找;
while(l < r)
{
mid = (l + r + 1) >> 1;
if(cntnum(mid) > n) r = mid - 1;
else l = mid;
}
return l;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
ll n;
scanf("%lld", &n);
if(n == 1) printf("1\n"); // 1 特判
else {
ll X = findx(n), num = cntnum(X), ans = (1 + ((n-num)*(X+1)))%mod; // 计算第一个1 和 最后缺少的 n - num 个 X + 1
ll tmp = 1;
for(int i = 1; X > 0; i++)
{
ll t = (X + 1) >> 1;
t = chen(t, t, 1);
ans = (ans + chen(t, i, tmp))%mod;
tmp = (tmp << 1) % mod;
X >>= 1;
}
printf("%lld\n", ans);
}
}
return 0;
}