Submission #65922009

---

Source Code Expand

#include <bits/stdc++.h>
#define all(c) c.begin(), c.end()
#define sz(c) ll(c.size())
#define ll long long
#define tr(a, it) for (auto it = a.begin(); it != a.end(); it++)
#define present(c, x) (c.find(x) != c.end())
#define cpresent(c, x) (find(all(c), x) != c.end())
#define vi vector<int>
#define vll vector<ll>
#define vvll vector<vll>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define pll pair<ll, ll>
#define inf 1e9
#define MOD 1000000007
#define MAXN 10000
#define madar 1e18
#define moda 998244353
#define loop(i, s, e) for (ll i = s; i < e; i++)
#define revloop(i, s, e) for (ll i = s; i >= e; i--)
#define newl cout << endl
#define pb push_back
#define f first
#define s second

using namespace std;

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ll gcd(ll a, ll b) {
    if (!(a % b)) return b;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

ll MSB(ll n) {
    ll ans = -1;
    while (n) {
        ans++;
        n /= 2;
    }
    return ans;
}

ll power(ll a, ll b, ll mod) {
    ll p = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1)
            p = (p * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return p;
}

ll inv_mod(ll n, ll mod) {
    return power(n, mod - 2, mod);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// #ifdef LOCAL
// #include "debug.h"
// #endif

ll N = 65;
vll fact(N + 1, 0);

void facto() {
    fact[0] = fact[1] = 1;

    for (ll i = 2; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % moda;
    }
}

ll nCr(ll n, ll r) {
    if (n < r || r < 0) return 0;
    ll numerator = fact[n];
    ll denominator = (fact[r] * fact[n - r]) % moda;
    return (numerator * inv_mod(denominator, moda)) % moda;
}

void solve(int tc) {
    ll n, k;
    cin >> n >> k;

    ll ans = 0;
    ll a = 0;

    ll pop = __builtin_popcountll(n);
    if (pop == k) {
        ans = n % moda;
    }

    for (ll b = 0; b < 62; b++) {
        if (n & (1ll << b)) {
            a++;

            ll rem = k - (pop - a);
            if (rem <= 0 || b < rem) continue;

            ll kk = ((1ll << b) - 1) % moda;
            ll pp = nCr(b - 1, rem - 1);
            ans = (ans + (kk * pp) % moda) % moda;

            ll hp = (n >> (b + 1)) << (b + 1);
            hp %= moda;
            ll kl = nCr(b, rem);
            ans = (ans + (kl * hp) % moda) % moda;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    facto();

    int t = 1;
    cin >> t;
    int tc = 0;
    while (t--) {
        tc++;
        solve(tc);
    }

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(int)’:
Main.cpp:88:16: warning: unused parameter ‘tc’ [-Wunused-parameter]
   88 | void solve(int tc) {
      |            ~~~~^~

Judge Result