QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378263#7927. Fortune Tellingkevinyang#WA 37ms3760kbC++2010.1kb2024-04-06 10:32:312024-04-06 10:32:31

Judging History

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

  • [2024-04-06 10:32:31]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:3760kb
  • [2024-04-06 10:32:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

/* Macros {{{ */
/*  A lot of this is from some of Benq's submissions
    [https://codeforces.com/profile/Benq]
    Ugly af to the eyes, but with vim fold its barable
    Hopefully c++20 concepts can make all this stuff must cleaner */

/* Basics {{{ */
using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define mp make_pair
#define fi first
#define se second

#define arr array
#define ve vector
using vi = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;

using vpi = vector<pi>;
using vpll = vector<pll>;
using vpld = vector<pld>;

using vvi = vector<vi>;
using vvll = vector<vll>;
using vvld = vector<vld>;

using vvpi = vector<vpi>;
using vvpll = vector<vpll>;
using vvpld = vector<vpld>;

#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz size()
#define rsz(a) resize(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, a, b) for (int i = a; i < b; ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define rep(a) For(_, 0, a)
#define each(a, x) for (auto &a : x)
#define reach(a, x) for (auto a = x.rbegin(); a != x.rend(); ++a)

template <typename T, typename U>
inline void cmin(T &x, U y) {
    if (y < x) x = y;
}
template <typename T, typename U>
inline void cmax(T &x, U y) {
    if (x < y) x = y;
}
/*}}}*/

/* IO {{{ */

/* Template Macros {{{ */
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
/*}}}*/

inline namespace Helpers { /*{{{*/
tcT, class = void > struct is_iterable : false_type {};
tcT > struct is_iterable<
          T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>
    : true_type {};
tcT > constexpr bool is_iterable_v = is_iterable<T>::value;

tcT, class = void > struct is_readable : false_type {};
tcT > struct is_readable<T, typename std::enable_if_t<is_same_v<
                                decltype(cin >> declval<T &>()), istream &>>>
    : true_type {};
tcT > constexpr bool is_readable_v = is_readable<T>::value;

tcT, class = void > struct is_printable : false_type {};
tcT > struct is_printable<T, typename std::enable_if_t<is_same_v<
                                 decltype(cout << declval<T>()), ostream &>>>
    : true_type {};
tcT > constexpr bool is_printable_v = is_printable<T>::value;
} /* namespace Helpers */
/*}}}*/

inline namespace Input { /*{{{*/
tcT > constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
tcTUU > void re(T &t, U &...u);
tcTU > void re(pair<T, U> &p); /* pairs */

/* re: read{{{ */
tcT > typename enable_if<is_readable_v<T>, void>::type re(T &x) {
    cin >> x;
} /* default */
tcT > typename enable_if<needs_input_v<T>, void>::type re(
          T &i);                                   // vectors, arrays, etc...
tcTU > void re(pair<T, U> &p) { re(p.fi, p.se); }  // pairs
tcT > typename enable_if<needs_input_v<T>, void>::type re(T &i) {
    each(x, i) re(x);
}
tcTUU > void re(T &t, U &...u) {
    re(t);
    re(u...);
} /* read multiple}}} */

/* rv: resize and read vectors{{{ */
void rv(size_t) {}
tcTUU > void rv(size_t N, ve<T> &t, U &...u);
template <class... U>
void rv(size_t, size_t N2, U &...u);
tcTUU > void rv(size_t N, ve<T> &t, U &...u) {
    t.rsz(N);
    re(t);
    rv(N, u...);
}
template <class... U>
void rv(size_t, size_t N2, U &...u) {
    rv(N2, u...);
} /*}}}*/

/* dumb shortcuts to read in ints{{{ */
void decrement() {} /* subtract one from each */
tcTUU > void decrement(T &t, U &...u) {
    --t;
    decrement(u...);
}
#define ints(...)    \
    int __VA_ARGS__; \
    re(__VA_ARGS__);
#define int1(...)      \
    ints(__VA_ARGS__); \
    decrement(__VA_ARGS__); /*}}}*/
} /* namespace Input */
/*}}}*/

inline namespace ToString { /*{{{*/
tcT > constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

/* ts: string representation to print */
tcT > typename enable_if<is_printable_v<T>, str>::type ts(T v) {
    stringstream ss;
    ss << fixed << setprecision(15) << v;
    return ss.str();
} /* default */
tcT > str bit_vec(T t) { /* bit vector to string */
    str res = "{";
    For(i, 0, t.sz) res += ts(t[i]);
    res += "}";
    return res;
}
str ts(ve<bool> v) { return bit_vec(v); }
template <size_t SZ>
str ts(bitset<SZ> b) {
    return bit_vec(b);
} /* bit vector */
tcTU > str ts(pair<T, U> p); /* pairs */
tcT > typename enable_if<needs_output_v<T>, str>::type ts(
          T v); /* vectors, arrays */
tcTU > str ts(pair<T, U> p) { return "(" + ts(p.fi) + ", " + ts(p.se) + ")"; }
tcT > typename enable_if<is_iterable_v<T>, str>::type ts_sep(T v, str sep) {
    /* convert container to string w/ separator sep */
    bool fst = 1;
    str res = "";
    for (const auto &x : v) {
        if (!fst) res += sep;
        fst = 0;
        res += ts(x);
    }
    return res;
}
tcT > typename enable_if<needs_output_v<T>, str>::type ts(T v) {
    return "{" + ts_sep(v, ", ") + "}";
}

/* for nested DS */
template <int, class T>
typename enable_if<!needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    return {ts(v)};
}
template <int lev, class T>
typename enable_if<needs_output_v<T>, ve<str>>::type ts_lev(const T &v) {
    if (lev == 0 || !v.sz) return {ts(v)};
    ve<str> res;
    for (const auto &t : v) {
        if (res.sz) res.back() += ",";
        ve<str> tmp = ts_lev<lev - 1>(t);
        res.insert(end(res), all(tmp));
    }
    For(i, 0, res.sz) {
        str bef = " ";
        if (i == 0) bef = "{";
        res[i] = bef + res[i];
    }
    res.back() += "}";
    return res;
}
} /* namespace ToString */
/*}}}*/

inline namespace Output { /*{{{*/
template <class T>
void pr_sep(ostream &os, str, const T &t) {
    os << ts(t);
}
template <class T, class... U>
void pr_sep(ostream &os, str sep, const T &t, const U &...u) {
    pr_sep(os, sep, t);
    os << sep;
    pr_sep(os, sep, u...);
}
/* print w/ no spaces */
template <class... T>
void pr(const T &...t) {
    pr_sep(cout, "", t...);
}
/* print w/ spaces, end with newline */
void ps() { cout << "\n"; }
template <class... T>
void ps(const T &...t) {
    pr_sep(cout, " ", t...);
    ps();
}
/* debug to cerr */
template <class... T>
void dbg_out(const T &...t) {
    pr_sep(cerr, " | ", t...);
    cerr << endl;
}
void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template <int lev, class T>
void dbgl_out(const T &t) {
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl;
}
} /* namespace Output */
/*}}}}}}}}}*/

int const Mod = 998244353;

ll modpow(ll a, ll b) {
    ll res = 1;
    for(ll e=1, p=a%Mod; e<=b; e<<=1, p=p*p%Mod)
        if(e&b) res = res*p%Mod;
    return res;
}

ll moddiv(ll a, ll b) {
    ll num = a%Mod, den = modpow(b, Mod-2), res = num*den%Mod;
    return res;
}


vvll memo;

ll dp(int loc, int cards) {
    if(loc == 0 && cards == 1) return 1;
    if(memo[loc][cards] >= 0) return memo[loc][cards];

    ll &res = memo[loc][cards];
    res = 0;

    for(int roll=0; roll<min(cards, 6); ++roll) {
        if(loc%6 == roll) continue;

        int num_cards_rmved = (cards-roll+5)/6;
        int num_cards_bef_loc_removed = (loc-roll+5)/6;

        res += moddiv(dp(loc - num_cards_bef_loc_removed, cards - num_cards_rmved), min(cards, 6));
    }

    res %= Mod;
    return res;
}

void solve() {
    int n;
    re(n);

    if(n <= 10000) {
        memo = vvll(n+10, vll(n+10, -1));
        for(int i=0; i<n; ++i) ps(dp(i, n));
    } else {
        rep(n) ps(moddiv(1, n));
    }

    // if(n <= 6 || n >= 36) {
    //     rep(n) ps(moddiv(1, n));
    //     return;
    // }
    //
    // for(int i=0; i<n; ++i) {
    //     ve<vvll> dp(n, vvll(n, vll(n, 0)));
    //     // dp[x][y][z] is probability that element i is at location x with y cards left in the deck after z moves
    //
    //
    //     dp[i][n-1][0] = 1;
    //     ll sum = dp[0][0][0];
    //
    //     for(int turn=0; turn+1<n; ++turn) {
    //         for(int cards=0; cards<6; ++cards) {
    //             for(int loc=0; loc<=cards; ++loc) {
    //                 for(int roll=0; roll<6; ++roll) {
    //                     if(loc%6 == roll) continue;
    //
    //                     int num_cards_rmved = (cards-roll+5)/6;
    //                     int num_cards_bef_loc_removed = (loc-roll+5)/6;
    //
    //                     dp[loc-num_cards_bef_loc_removed][cards-num_cards_rmved][turn+1] += moddiv(dp[loc][cards][turn], cards+1);
    //                     dp[loc-num_cards_bef_loc_removed][cards-num_cards_rmved][turn+1] %= Mod;
    //                 }
    //             }
    //         }
    //
    //         for(int cards=6; cards<n; ++cards) {
    //             for(int loc=0; loc<n; ++loc) {
    //                 for(int roll=0; roll<6; ++roll) {
    //                     if(loc%6 == roll) continue;
    //
    //                     int num_cards_rmved = (cards-roll+5)/6;
    //                     int num_cards_bef_loc_removed = (loc-roll+5)/6;
    //
    //                     dp[loc-num_cards_bef_loc_removed][cards-num_cards_rmved][turn+1] += moddiv(dp[loc][cards][turn], 6);
    //                     dp[loc-num_cards_bef_loc_removed][cards-num_cards_rmved][turn+1] %= Mod;
    //                 }
    //             }
    //         }
    //
    //         sum += dp[0][0][turn+1];
    //         sum %= Mod;
    //     }
    //
    //     ps(sum);
    // }
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    /* cout << fixed << setprecision(6); */
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

input:

3

output:

332748118
332748118
332748118

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

7

output:

305019108
876236710
876236710
876236710
876236710
876236710
305019108

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

8

output:

64701023
112764640
160828257
160828257
160828257
160828257
112764640
64701023

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

10

output:

409773145
853745402
299473306
743445563
189173467
189173467
743445563
299473306
853745402
409773145

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

11

output:

989514850
873566509
757618168
641669827
525721486
409773145
525721486
641669827
757618168
873566509
989514850

result:

ok 11 lines

Test #6:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

12

output:

175103562
138336949
101570336
64803723
28037110
989514850
989514850
28037110
64803723
101570336
138336949
175103562

result:

ok 12 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

13

output:

159099473
484299138
167572226
849089667
532362755
215635843
175103562
215635843
532362755
849089667
167572226
484299138
159099473

result:

ok 13 lines

Test #8:

score: -100
Wrong Answer
time: 37ms
memory: 3756kb

input:

131091

output:

613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
613159054
...

result:

wrong answer 1st lines differ - expected: '567383016', found: '613159054'