记录一下这个神奇的套路。
首先有 \(\operatorname{popcount}(n) = n - \sum\limits_{i=1}^{\infty} \left\lfloor\frac{n}{2^i}\right\rfloor\)。证一下:
\[\operatorname{popcount}(n) = \sum\limits_{i=0}^{\infty} \left\lfloor\dfrac{n}{2^i}\right\rfloor \bmod 2
\]
\[= \sum\limits_{i=0}^{\infty} \left\lfloor\dfrac{n}{2^i}\right\rfloor - 2 \left\lfloor\dfrac{n}{2^{i+1}}\right\rfloor
\]
\[= \sum\limits_{i=0}^{\infty} \left\lfloor\dfrac{n}{2^i}\right\rfloor - 2\sum\limits_{i=1}^{\infty} \left\lfloor\dfrac{n}{2^i}\right\rfloor
\]
\[= n - \sum\limits_{i=1}^{\infty} \left\lfloor\dfrac{n}{2^i}\right\rfloor
\]
设 \(t = \left\lfloor\frac{n-r}{m}\right\rfloor\),答案为:
\[\sum\limits_{i=0}^t \operatorname{popcount}(mi + r)
\]
\[= \sum\limits_{i=0}^t mi + r - \sum\limits_{k=1}^{\infty} \left\lfloor\dfrac{mi + r}{2^k}\right\rfloor
\]
\[= m\left\lfloor\dfrac{t(t+1)}{2}\right\rfloor + (t+1)r - \sum\limits_{k=1}^{\infty} \sum\limits_{i=0}^t \left\lfloor\dfrac{mi + r}{2^k}\right\rfloor
\]
至此后面部分可以类欧计算。
code
// Problem: Ex - Popcount Sum
// Contest: AtCoder - UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283)
// URL: https://atcoder.jp/contests/abc283/tasks/abc283_h
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
ll dfs(ll a, ll b, ll c, ll n) {
if (!a || !n) {
return (n + 1) * (b / c);
}
if (n < 0) {
return 0;
}
if (a >= c || b >= c) {
return dfs(a % c, b % c, c, n) + (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
}
ll m = (a * n + b) / c;
return m * n - dfs(c, c - b - 1, a, m - 1);
}
void solve() {
ll n, a, b;
scanf("%lld%lld%lld", &n, &a, &b);
ll m = (n - b) / a;
ll ans = a * m * (m + 1) / 2 + (m + 1) * b;
for (int i = 1; (1LL << i) <= n; ++i) {
ans -= dfs(a, b, 1LL << i, m);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Popcount AtCoder Contest 283beginner popcount atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310