题解：P14074 [GESP202509 五级] 有趣的数字和

· · 题解

打表+枚举

题目大意

统计区间 [l,r] 内所有二进制表示中包含奇数个 1 的整数之和。

思路分析

根据题意，使用如下的暴力枚举可以轻松通过 40% 的数据，但是剩余的数据，可能就TLE了。这是因为我们的枚举量太大，可能达到 10^9。

ll ans=0;
for(ll i=l;i<=r;i++){
  ll cnt=0,t=i;      
  while(t){
    if(t&1) cnt++;
    t>>=1;
  }
  if(cnt&1) ans+=i;   
}
cout<<ans;

那要怎么优化呢？枚举优化的一个常见策略是打表，首先离线预处理一部分数据，存进数组里，后续计算时直接使用，减少枚举量。

结合本题数据规模分析，我们可以预处理计算出 1\sim10^9 长度为 10^7 的每一段数据，如图所示：

根据前缀和的思想，还可以将本题 [l,r] 区间上的问题，转化为求解 [1,r]-[1,l-1]。

因此，可以使用如下代码预处理出 [1,n] 的有趣的数的和，并输出到控制台，其中 n \text{ 是 } 10^7 \text{ 的倍数，且 } n \leq 10^9。

ll l=1,r=1e7,pre=0;  // pre 保存前一个区间的和 
while(r<=1e9+3e7){   
  ll ans=0;
  for(ll i=l;i<=r;i++){
    ll cnt=0,t=i;
    while(t){      
      if(t&1) cnt++;
      t>>=1;
    }
    if(cnt&1) ans+=i;
  }
  ans+=pre;
  pre=ans;
  cout<<ans<<",";
  r+=1e7;
  l+=1e7;
}

最后，使用这些预处理数据，拼凑答案即可。

即将 [1,n] 划分为 [1,l] 和 [l+1,n]，其中 [1,l] 已经预处理得出，[l+1,n] 暴力枚举，[l+1,n] 区间大小不超过 10^7，暴力枚举不会超时。

ll pre[]={0,24999997500000,...};// 打表

ll calc(ll n){ 
    ll ans=0;
    ll l=n/10000000*10000000;
    for(ll i=l+1;i<=n;i++){
        ll cnt=0,t=i;
        while(t){
            if(t&1) cnt++;
            t>>=1;
        }
        if(cnt&1) ans+=i;
    }
    return ans+pre[n/10000000];
}

void solov(){
    ll l,r;
    cin>>l>>r;
    cout<<calc(r)-calc(l-1);
}

AC Code

#include<bits/stdc++.h>/
#define quick_read ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long int ll;
ll pre[]={0,24999997500000,99999995000000,224999992500000,399999990000000,624999987500000,899999985000000,1225000052500000,1599999980000000,2025000067500000,2499999975000000,3025000082500000,3599999970000000,4224999967500000,4900000105000000,5624999962500000,6399999960000000,7224999957500000,8100000135000000,9024999952500000,9999999950000000,11024999947500000,12100000165000000,13224999942500000,14399999940000000,15625000187500000,16899999935000000,18225000202500000,19600000210000000,21024999927500000,22499999925000000,24024999922500000,25599999920000000,27225000247500000,28899999915000000,30624999912500000,32400000270000000,34225000277500000,36099999905000000,38024999902500000,39999999900000000,42025000307500000,44099999895000000,46225000322500000,48400000330000000,50624999887500000,52899999885000000,55225000352500000,57599999880000000,60025000367500000,62500000375000000,65024999872500000,67599999870000000,70225000397500000,72900000405000000,75625000412500000,78400000420000000,81225000427500000,84099999855000000,87025000442500000,89999999850000000,93025000457500000,96099999845000000,99224999842500000,102399999840000000,105624999837500000,108900000495000000,112224999832500000,115599999830000000,119025000517500000,122499999825000000,126025000532500000,129600000540000000,133224999817500000,136900000555000000,140624999812500000,144399999810000000,148224999807500000,152099999805000000,156025000592500000,159999999800000000,164024999797500000,168100000615000000,172225000622500000,176399999790000000,180625000637500000,184900000645000000,189224999782500000,193600000660000000,198024999777500000,202499999775000000,207025000682500000,211599999770000000,216225000697500000,220900000705000000,225625000712500000,230399999760000000,235225000727500000,240100000735000000,245025000742500000,250000000750000000,255025000757500000,260099999745000000,265225000772500000};
ll calc(ll n){
    ll ans=0;
    ll l=n/10000000*10000000;
    for(ll i=l+1;i<=n;i++){
        ll cnt=0,t=i;
        while(t){
            if(t&1) cnt++;
            t>>=1;
        }
        if(cnt&1) ans+=i;
    }
    return ans+pre[n/10000000];
}
void solov(){
    ll l,r;
    cin>>l>>r;
    cout<<calc(r)-calc(l-1);
}
int main(){
    quick_read;
    solov();
    return 0;
}