题意: 从奇数列 1 3 5 7 9 .... 偶数列 2 4 6 8 10... 分别轮流取 1 2 4 ....2^n 个数构成新数列 求新数列的区间和 (就一次询问)
思路: 首先单次区间和就是一个简单的类似前缀和就可以搞定 那么如何求新数列的和呢
我们明确一个观点: 原数列的区间和结果显而易见 那么题目就转化成 奇数列和偶数列分别取了多少个数
因为取数的数字的以 2 的幂递增的, 所以 l r(<=1e18) log2(1e18) 很简单过
而有了数量结果可以用 0(1) 的时间算出来
记得瞎 MOD 和 LL
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int mod=1e9+7;
- ll solve(ll x){
- int flag=0;
- ll sum=0;
- ll sumodd=0,sumeven=0;
- ll i;
- if(x<=0)return 0;
- for(i=1;;i<<=1){
- sum+=i;
- if(sum>x){
- sum-=i;
- if(flag==0)sumodd+=(x-sum);
- else sumeven+=(x-sum);
- break;
- }
- if(flag==0)sumodd+=i;
- else sumeven+=i;
- flag^=1;
- }
- return ( (sumodd%mod)*(sumodd%mod)+(sumeven+1)%mod*(sumeven%mod))%mod;
- }
- int main(){
- ll l,r;
- cin>>l>>r;
- cout<<(solve(r)-solve(l-1)+mod)%mod<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3041016.html