Untitled
unknown
c_cpp
a year ago
1.6 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; #define int int64_t const int MOD = 1e9 + 7; int mpow(int x, int y) { int res = 1; if (x == 0)return 0; while (y > 0) { if (y % 2) res = (res * x); y /= 2; x = (x * x); } return res; } void solve() { int n, k; cin >> n >> k; int curr = 0, prev = 0; bool flag = 1; int ans = 0; while(prev < n) { if(flag) { for(int i = 0; i < 62 && __builtin_popcountll(curr) <= k; i++) { if(!(mpow(2, i) & curr)) { curr += mpow(2, i); } } curr = min(curr, n); int x = (curr - prev) % MOD; x *= (x + 1); if(x % 2) x += MOD; x /= 2; ans += x; ans %= MOD; } else { int start = __lg(curr) + 1; int store = __builtin_ctzll(curr); curr -= mpow(2, store); if(__builtin_popcountll(curr) + __builtin_ctzll(curr) == start) { curr = mpow(2, start); } else { int pos = __builtin_ctzll(curr); while(curr & mpow(2, pos)) { curr -= mpow(2, pos); pos++; } curr += mpow(2, pos); } curr = min(curr, n); } flag ^= 1; prev = curr; } cout << ans << '\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int _aditya_b = 1; cin >> _aditya_b; while (_aditya_b--) solve(); }
Editor is loading...
Leave a Comment