题解 P5177 【签到】

Eric1031 · 2019-01-07 20:59:04 · 题解

对大佬的代码表示无限懵逼……

这道题目思维有点毒瘤，因为logn都会超时，从头讲吧。

对两个数i，j不妨设i>j，令h=i^j，则j最高位不能为i的最高位，否则h<j,当满足这一条件时,h一定大于j,其次，要让h<i,那么（经过多次尝试）只要对i第二1处，j在此取最高位，后面随便取，我们神奇地发现，它代表的正好是该位代表的数字，同理对第3，第4……

于是，一个数代表的就是它减去最高位！

然后，就好办了……

#include<bits/stdc++.h>
using namespace std;
long long q[101],n,b[101],sum,bit;
int t,l;
const long long mod=1000000007,inv=500000004;
long long num(long long x)
{
    long long h=(((((x+1)%mod)*x)%mod)*inv)%mod;
    return h;
}//等差数列求和
int main()
{
    b[1]=1;
     for(int i=2;i<64;i++)
     { 
        b[i]=b[i-1]<<1;
        q[i]=num(((1ll<<(i-1))-1)%mod);
        q[i]=(q[i]+q[i-1])%mod;//求2^i的情况数
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        for(bit=63;bit>=1;bit--)
        { 
            if(n>b[bit])break;
        }//倒着求，不然会T
        n-=(1ll<<(bit-1)); 
        sum=q[bit-1];
        sum=(sum+num(n%mod))%mod;
        sum=(sum*2)%mod;
        printf("%lld\n",sum);
    }
}