Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: E - Popcount Sum 3
- // Contest: AtCoder - Panasonic Programming Contest 2025（AtCoder Beginner Contest 406）
- // URL: https://atcoder.jp/contests/abc406/tasks/abc406_e
- // Memory Limit: 1024 MB
- // Time Limit: 2000 ms
- //
- // Powered by CP Editor (https://cpeditor.org)
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- namespace rngs = std::ranges;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- constexpr ll mod = 998244353;
- // map<a2l, ll> cache;
- /*
- ll search(ll n, ll k, ll len)
- {
- if (k < 0)
- return 0;
- if (len + 1 < k)
- return 0;
- if (k == 0)
- return 1;
- ll ans = 0;
- if (n > (1ll << len))
- ans = search(n - (1ll << len), k - 1, len - 1);
- ans = (ans + search(n, k - 1, len - 1)) % mod;
- return ans;
- // return (search(n - (1ll << len), k - 1, len - 1) + search(n - (1ll << len), k, len - 1)) % mod;
- }
- */
- string a;
- vector<vl> f;
- int dfs(int u, int st, bool lead, bool op)
- {
- if (st < 0)
- return 0;
- if (u == 0)
- return 1;
- dbg(u, st, lead, op, f[u][st]);
- if (!op && !lead && ~f[u][st])
- return f[u][st];
- int up = op ? a[u] - '0' : 1;
- int ans = 0;
- if (st == 0)
- ans = 1;
- else
- for (int i = 0; i <= up; i++) {
- ans = (ans + dfs(u - 1, st - i, lead && i == 0, op && i == a[u])) % mod;
- }
- if (!op && !lead)
- f[u][st] = ans;
- return ans;
- }
- void solve()
- {
- ll t;
- cin >> t;
- for (ll i = 0, n, k; i < t; ++i) {
- cin >> n >> k;
- a = "";
- for (ll v = n; v; v = v / 2)
- a.push_back(v % 2 + '0');
- // reverse(a.begin(), a.end());
- ll u = a.size();
- // a = '0' + a;
- f = vector<vl>(u, vl(k + 1, -1));
- dbg(a);
- cout << dfs(u - 1, k, true, true) << '\n';
- }
- }
- int main(int argc, char **argv)
- {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- solve();
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
