Atcoder abc283

https://atcoder.jp/contests/abc283/tasks

Ex - Popcount Sum

$0 \le R,M+R,2M+R,3M+R,\cdots < N$

$R \in [0,M]$

问上述[0,N]中的这些数, 的二进制下的1的个数的总数

范围

t 组数据 1e5

n 1e9

4s

1024mb

我的思路

分类一下, 感觉就需要一点数学, 然后t 1e5, 基本也就是说, 要么O 1,要么O sqrt 左右

如果m==1, 那么就是1…n 的所有数的二进制1的个数和, [1…2^t,2^t+1…n] 这样划分就是 sqrt

如果m==2^k, 那么这些数的 低k位都一样, k位以上, 和上面是一样的

如果m 不是上面的情况,进位的时刻, 似乎并不好拿捏

2, 3+2,6+2,9+2

  10
 101
1000
1011
1110

能说的是 低两位4次的循环节, 比3还大, 高位也没啥规律

---

对称相加

R, M+R, 2M+R, … , kM+R

kM+R, (k-1)M+R,…, R

对称的和始终是 (k+1)M+R, 有办法 只算 一半 与 (k+1)M+R 的bit的联系, 这样一半

题解

对于每个bit单独 考虑!!!!!!

变成 计算 R,M+R,2M+R,3M+R… 中 二进制第k位 为1的个数

---

A & (1<<k)

等价于

A % 2^{k+1} \in [2^k,2^{k+1})

等价于

$\lfloor \frac{A+2^k}{2^{k+1}} \rfloor - \lfloor \frac{A}{2^{k+1}} \rfloor = 1$ (整除)

然后就可以 floor sum了!?

注意到上面 有bit时, = 1, 否则 = 0

所以 $= \sum_A (\lfloor \frac{A+2^k}{2^{k+1}} \rfloor - \lfloor \frac{A}{2^{k+1}} \rfloor )$

$= (\sum_A \lfloor \frac{A+2^k}{2^{k+1}} \rfloor )-(\sum_A \lfloor \frac{A}{2^{k+1}} \rfloor )$

代码

https://atcoder.jp/contests/abc283/submissions/37863204

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

// \sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor
ll floor_sum(ll a,ll b,ll c,ll n){
  if(a==0) return (b/c)*(n+1);
  if(a >= c or b >= c) return n*(n+1)/2*(a/c) + (n+1)*(b/c) + floor_sum(a%c,b%c,c,n);
  ll m = (a*n+b)/c;
  return m*n - floor_sum(c,c-b-1,a,m-1);
}

int main(){
  int t=read();
  while(t--){
    int n=read();
    int m=read();
    int r=read();
    ll ans=0;
    rep(p,0,30){ // 2^30 > 10^9
      // = sum((value+2^p)/(2^{p+1}) - (value)/(2^{p+1}))
      ans += floor_sum(m,r+(1<<p),1<<(p+1),(n-r)/m);
      ans -= floor_sum(m,r       ,1<<(p+1),(n-r)/m);
    }
    printf("%lld\n",ans);
  }
  return 0;
}

总结

Ex

又学一个 floor sum

参考

官方题解

https://codeforces.com/blog/entry/97562

http://poj.org/problem?id=3495