QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378263 | #7927. Fortune Telling | kevinyang# | WA | 37ms | 3760kb | C++20 | 10.1kb | 2024-04-06 10:32:31 | 2024-04-06 10:32:31 |
Judging History
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'