汉明的重量

想起还有道CF计数题没补…

题意是求，jls的取模整数板子好像有些问题。

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

using ll = long long;
// assume -P <= x < 2P
const int P = 998244353, mod = P;

int powmod(int a, int b)
{
    int res = 1;
    for (; b > 0; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1)
            res = 1ll * res * a % mod;
    return res;
}

template <int MOD, int RT>
struct mint
{
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v;
    explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() : v(0) {}
    mint(ll _v)
    {
        v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0)
            v += MOD;
    }
    bool operator==(const mint &o) const
    {
        return v == o.v;
    }
    friend bool operator!=(const mint &a, const mint &b)
    {
        return !(a == b);
    }
    friend bool operator<(const mint &a, const mint &b)
    {
        return a.v < b.v;
    }

    mint &operator+=(const mint &o)
    {
        if ((v += o.v) >= MOD)
            v -= MOD;
        return *this;
    }
    mint &operator-=(const mint &o)
    {
        if ((v -= o.v) < 0)
            v += MOD;
        return *this;
    }
    mint &operator*=(const mint &o)
    {
        v = int((ll)v * o.v % MOD);
        return *this;
    }
    mint &operator/=(const mint &o) { return (*this) *= inv(o); }
    friend mint pow(mint a, ll p)
    {
        mint ans = 1;
        assert(p >= 0);
        for (; p; p /= 2, a *= a)
            if (p & 1)
                ans *= a;
        return ans;
    }
    friend mint inv(const mint &a)
    {
        assert(a.v != 0);
        return pow(a, MOD - 2);
    }

    mint operator-() const { return mint(-v); }
    mint &operator++() { return *this += 1; }
    mint &operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint &b) { return a += b; }
    friend mint operator-(mint a, const mint &b) { return a -= b; }
    friend mint operator*(mint a, const mint &b) { return a *= b; }
    friend mint operator/(mint a, const mint &b) { return a /= b; }
};

using Z = mint<mod, 3>;
Z inv2;
Z cal(ll n)
{
    Z ans = Z(n)*Z(n+1)*inv2*61;
    for (int i = 0; i < 61; ++i)
    {
        ll bs = 1ll << (i + 1);
        ll cnt = n / bs;
        Z qsb = 0;
        if(cnt){
            qsb += Z(cnt) * Z(bs * (cnt - 1)) * Z((1ll<<i)) * inv2;
            qsb += Z(cnt) * Z(1ll<<i) * Z((1ll<<i)-1) * inv2;
        }
        ll nxt=n;
        if (n & (1ll << i))nxt=nxt/(1ll << i)*((1ll << i))-1ll;

        {
            Z fr = nxt / bs * bs;
            Z bkcn =( nxt & ((1ll<<i) - 1)) + 1ll;
            //cerr<<fr<<"::"<<(nxt & ((1ll<<i) - 1))<<"\n";
            qsb += (bkcn) * Z(fr);
            qsb += (bkcn) * (bkcn - 1) * inv2;
        }

        ans -= qsb;
    }
    return ans;
}
ll tt, n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    inv2=inv(Z(2));
    cin >> tt;
    f(sb, 1, tt)
    {
        cin >> n;
        cout << (cal(n)).v << "\n";
    }
    return 0;
}