QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75540#5464. Dice Gamerin204WA 2ms3440kbC++1714.0kb2023-02-05 16:59:092023-02-05 16:59:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 16:59:12]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：3440kb
查看
  • [2023-02-05 16:59:09]
  • 提交

answer

#line 1 "A.cpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));

#define endl "\n"
#define spa ' '
#define len(A) A.size()
#define all(A) begin(A), end(A)

#define fori1(a) for(ll _ = 0; _ < (a); _++)
#define fori2(i, a) for(ll i = 0; i < (a); i++)
#define fori3(i, a, b) for(ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

template <typename T>
vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){
    vector<tuple<ll, T>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){
    vector<tuple<ll, char>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

#define enum1(A) fori(A.size())
#define enum2(a, A) for(auto a:A)
#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))
#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))
#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)

template <typename T, typename S>
vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){
    int n = min(A.size(), B.size());
    vector<tuple<T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};
    return ret;
}

template <typename T, typename S>
vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){
    int n = min(A.size(), B.size());
    vector<tuple<ll, T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};
    return ret;
}

#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))
#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))
#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))
#define overload6(a, b, c, d, e, f, g, ...) g
#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)

vector<char> stoc(string &S){
    int n = S.size();
    vector<char> ret(n);
    for(int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}

#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);

const ll MOD1 = 1000000007;
const ll MOD9 = 998244353;

template<class T> auto min(const T& a){
    return *min_element(all(a));
}
template<class T> auto max(const T& a){
    return *max_element(all(a));
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

void FLUSH(){cout << flush;}
void print(){cout << endl;}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(forward<Tail>(tail)...);
}
template<typename T>
void print(vector<T> &A){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i == n - 1) cout << endl;
        else cout << spa;
    }
}
template<typename T>
void print(vector<vector<T>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void print(pair<T, S> &A){
    cout << A.first << spa << A.second << endl;
}
template<typename T, typename S>
void print(vector<pair<T, S>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void prisep(vector<T> &A, S sep){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i == n - 1) cout << endl;
        else cout << sep;
    }
}
template<typename T, typename S>
void priend(T A, S end){
    cout << A << end;
}
template<typename T>
void priend(T A){
    priend(A, spa);
}
template<class... T>
void inp(T&... a){
    (cin >> ... >> a);
}
template<typename T>
void inp(vector<T> &A){
    for(auto &a:A) cin >> a;
}
template<typename T>
void inp(vector<vector<T>> &A){
    for(auto &row:A) inp(row);
}
template<typename T, typename S>
void inp(pair<T, S> &A){
    inp(A.first, A.second);
}
template<typename T, typename S>
void inp(vector<pair<T, S>> &A){
    for(auto &row: A) inp(row.first, row.second);
}

template<typename T>
T sum(vector<T> &A){
    T tot = 0;
    for(auto a:A) tot += a;
    return tot;
}

template<typename T>
pair<vector<T>, map<T, int>> compression(vector<T> X){
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    map<T, int> mp;
    for(int i = 0; i < X.size(); i++) mp[X[i]] = i;
    return {X, mp};
}

#line 2 "Library/C++/other/Modint.hpp"

template<int MOD>
struct Modint{
    int x;
    Modint() : x(0){}
    Modint(int64_t y){
        if(y >= 0) x = y % MOD;
        else x = (y % MOD + MOD) % MOD;
    }

    Modint &operator+=(const Modint &p){
        x += p.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }

    Modint &operator-=(const Modint &p){
        x -= p.x;
        if(x < 0) x += MOD;
        return *this;
    }

    Modint &operator*=(const Modint &p){
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Modint &operator/=(const Modint &p){
        *this *= p.inverse();
        return *this;
    }

    Modint &operator%=(const Modint &p){
        assert(p.x == 0);
        return *this;
    }

    Modint operator-() const{
        return Modint(-x);
    }

    Modint& operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Modint& operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }

    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }

    friend Modint operator+(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) += rhs;
    }

    friend Modint operator-(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) -= rhs;
    }

    friend Modint operator*(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) *= rhs;
    }

    friend Modint operator/(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) /= rhs;
    }

    friend Modint operator%(const Modint &lhs, const Modint &rhs){
        assert(rhs.x == 0);
        return Modint(lhs);
    }

    bool operator==(const Modint &p) const{
        return x == p.x;
    }

    bool operator!=(const Modint &p) const{
        return x != p.x;
    }

    bool operator<(const Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Modint &rhs) {
        return x >= rhs.x;
    }

    Modint inverse() const{
        int a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return Modint(u);
    }

    Modint pow(int64_t k) const{
        Modint ret(1);
        Modint y(x);
        while(k > 0){
            if(k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Modint &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, Modint &p){
        int64_t y;
        is >> y;
        p = Modint<MOD>(y);
        return (is);
    }

    static int get_mod(){
        return MOD;
    }
};

struct Arbitrary_Modint{
    int x;
    static int MOD;

    static void set_mod(int mod){
        MOD = mod;
    }

    Arbitrary_Modint() : x(0){}
    Arbitrary_Modint(int64_t y){
        if(y >= 0) x = y % MOD;
        else x = (y % MOD + MOD) % MOD;
    }

    Arbitrary_Modint &operator+=(const Arbitrary_Modint &p){
        x += p.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }

    Arbitrary_Modint &operator-=(const Arbitrary_Modint &p){
        x -= p.x;
        if(x < 0) x += MOD;
        return *this;
    }

    Arbitrary_Modint &operator*=(const Arbitrary_Modint &p){
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Arbitrary_Modint &operator/=(const Arbitrary_Modint &p){
        *this *= p.inverse();
        return *this;
    }

    Arbitrary_Modint &operator%=(const Arbitrary_Modint &p){
        assert(p.x == 0);
        return *this;
    }

    Arbitrary_Modint operator-() const{
        return Arbitrary_Modint(-x);
    }

    Arbitrary_Modint& operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Arbitrary_Modint& operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Arbitrary_Modint operator++(int) {
        Arbitrary_Modint result = *this;
        ++*this;
        return result;
    }

    Arbitrary_Modint operator--(int) {
        Arbitrary_Modint result = *this;
        --*this;
        return result;
    }

    friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) += rhs;
    }

    friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) -= rhs;
    }

    friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) *= rhs;
    }

    friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) /= rhs;
    }

    friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        assert(rhs.x == 0);
        return Arbitrary_Modint(lhs);
    }

    bool operator==(const Arbitrary_Modint &p) const{
        return x == p.x;
    }

    bool operator!=(const Arbitrary_Modint &p) const{
        return x != p.x;
    }

    bool operator<(const Arbitrary_Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Arbitrary_Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Arbitrary_Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Arbitrary_Modint &rhs) {
        return x >= rhs.x;
    }

    Arbitrary_Modint inverse() const{
        int a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return Arbitrary_Modint(u);
    }

    Arbitrary_Modint pow(int64_t k) const{
        Arbitrary_Modint ret(1);
        Arbitrary_Modint y(x);
        while(k > 0){
            if(k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, Arbitrary_Modint &p){
        int64_t y;
        is >> y;
        p = Arbitrary_Modint(y);
        return (is);
    }

    static int get_mod(){
        return MOD;
    }
};
int Arbitrary_Modint::MOD = 998244353;

using modint9 = Modint<998244353>;
using modint1 = Modint<1000000007>;
using modint = Arbitrary_Modint;
#line 186 "A.cpp"
using mint = modint9;

void solve(){
    LL(n);
    ll m = n - 1;
    vec(int, ind, 0);
    fori(i, 30){
        if((n >> i) & 1) ind.push_back(i);
    }

    auto bitcnt=[&](ll n){
        ll m = n - 1;
        vec(ll, cnt, 30);
        fori(i, 30){
            cnt[i] = (m >> i + 1) << i;
            cnt[i] += max(0LL, m % (1LL << i + 1) - (1LL << i) + 1);
        }
        return cnt;
    };

    auto cnt = bitcnt(n);

    auto calc=[&](ll x){
        ll tot = 0;
        fori(i, 30){
            if((x >> i) & 1) tot += (1LL << i) * (n - cnt[i]);
            else tot += (1LL << i) * cnt[i];
        }
        return tot;
    };

    auto f=[&](auto &&self, ll l, ll r) -> mint {
        ll l_ = calc(l);
        if(l + 1 == r){
            return mint(max(l_, l * n));
        }
        ll r_ = calc(r - 1);
        bool fl = (l_ < l * n);
        bool fr = (r_ < r * n);
        if(fl != fr){
            ll mid = (l + r) >> 1;
            return self(self, l, mid) + self(self, mid, r);
        }
        else if(fl){
            return mint(r - l) * mint(l + r - 1) / 2 * mint(n);
        }
        else{
            auto c1 = bitcnt(r);
            auto c2 = bitcnt(l);
            mint tot = 0;
            fori(i, 30){
                tot += mint(1LL << i) * mint(c2[i] - c1[i]) * mint(n - cnt[i]);
                tot += mint(1LL << i) * mint((r - l) - (c2[i] - c1[i])) * mint(cnt[i]);
                return tot;
            }
        }
    };

    reverse(all(ind));
    mint ans = 0;
    ll l = 0;
    for(auto i:ind){
        ll r = l | (1LL << i);
        ans += f(f, l, r);
        l = r;
    }
    ans /= mint(n).pow(2);
    print(ans);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3440kb

input:

4
1
2
3
4

output:

0
249561089
776412276
2

result:

ok 4 number(s): "0 249561089 776412276 2"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3420kb

input:

100
119
75
29
10
17
29
449
71
72
12
79
117
83
80
35
272
105
497
346
287
362
140
297
167
111
419
210
212
170
413
373
210
196
39
1
101
258
496
333
293
392
2
187
431
157
342
436
106
449
136
378
243
357
325
237
254
22
292
62
435
18
446
471
18
42
377
181
350
19
389
212
58
45
70
52
63
107
71
66
355
381
30...

output:

513537937
976061162
995870418
858490148
759909203
995870418
725699402
133864964
255723109
83187034
526713467
804341865
915793936
354376763
34225532
803517705
143330720
992295702
909273304
42708047
237030182
774148721
207041074
884635883
489926473
685592679
475354521
117717563
751619313
948879175
926...

result:

wrong answer 1st numbers differ - expected: '645006489', found: '513537937'
English 繁體中文 简体中文

Server Time: 2024-12-03 19:43:22 | OpenSource Project