結果
問題 | No.2816 At Most Two Moves |
ユーザー | Fu_L |
提出日時 | 2024-07-19 22:36:04 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 4,684 bytes |
コンパイル時間 | 5,559 ms |
コンパイル使用メモリ | 274,276 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 22:36:11 |
合計ジャッジ時間 | 6,345 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 4 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 4 ms
5,376 KB |
testcase_14 | AC | 4 ms
5,376 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 4 ms
5,376 KB |
testcase_19 | AC | 4 ms
5,376 KB |
testcase_20 | AC | 3 ms
5,376 KB |
testcase_21 | AC | 3 ms
5,376 KB |
testcase_22 | AC | 3 ms
5,376 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 4 ms
5,376 KB |
testcase_25 | AC | 3 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; #define rep(i, a, b) for(ll i = a; i < b; ++i) #define rrep(i, a, b) for(ll i = a; i >= b; --i) constexpr ll inf = 4e18; struct SetupIO { SetupIO() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(30); } } setup_io; template <uint32_t m> struct StaticModint { using mint = StaticModint; static constexpr uint32_t mod() { return m; } static constexpr mint raw(uint32_t v) { mint a; a._v = v; return a; } constexpr StaticModint() : _v(0) {} template <class T> constexpr StaticModint(const T& v) { static_assert(is_integral_v<T>); if constexpr(is_signed_v<T>) { int64_t x = int64_t(v % int64_t(m)); if(x < 0) x += m; _v = uint32_t(x); } else _v = uint32_t(v % m); } constexpr uint32_t val() const { return _v; } constexpr mint& operator++() { return *this += 1; } constexpr mint& operator--() { return *this -= 1; } constexpr mint operator++(int) { mint res = *this; ++*this; return res; } constexpr mint operator--(int) { mint res = *this; --*this; return res; } constexpr mint& operator+=(mint rhs) { if(_v >= m - rhs._v) _v -= m; _v += rhs._v; return *this; } constexpr mint& operator-=(mint rhs) { if(_v < rhs._v) _v += m; _v -= rhs._v; return *this; } constexpr mint& operator*=(mint rhs) { return *this = *this * rhs; } constexpr mint& operator/=(mint rhs) { return *this *= rhs.inv(); } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint{} - *this; } constexpr mint pow(long long n) const { assert(0 <= n); if(n == 0) return 1; mint x = *this, r = 1; while(1) { if(n & 1) r *= x; n >>= 1; if(n == 0) return r; x *= x; } } constexpr mint inv() const { if constexpr(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } } friend constexpr mint operator+(mint lhs, mint rhs) { return lhs += rhs; } friend constexpr mint operator-(mint lhs, mint rhs) { return lhs -= rhs; } friend constexpr mint operator*(mint lhs, mint rhs) { return uint64_t(lhs._v) * rhs._v; } friend constexpr mint operator/(mint lhs, mint rhs) { return lhs /= rhs; } friend constexpr bool operator==(mint lhs, mint rhs) { return lhs._v == rhs._v; } friend constexpr bool operator!=(mint lhs, mint rhs) { return lhs._v != rhs._v; } friend istream& operator>>(istream& in, mint& x) { long long a; in >> a; x = a; return in; } friend ostream& operator<<(ostream& out, const mint& x) { return out << x.val(); } private: uint32_t _v = 0; static constexpr bool prime = []() -> bool { if(m == 1) return 0; if(m == 2 or m == 7 or m == 61) return 1; if(m % 2 == 0) return 0; uint32_t d = m - 1; while(d % 2 == 0) d /= 2; for(uint32_t a : {2, 7, 61}) { uint32_t t = d; mint y = mint(a).pow(t); while(t != m - 1 && y != 1 && y != m - 1) { y *= y; t <<= 1; } if(y != m - 1 && t % 2 == 0) return 0; } return 1; }(); static constexpr pair<int32_t, int32_t> inv_gcd(int32_t a, int32_t b) { if(a == 0) return {b, 0}; int32_t s = b, t = a, m0 = 0, m1 = 1; while(t) { const int32_t u = s / t; s -= t * u; m0 -= m1 * u; swap(s, t); swap(m0, m1); } if(m0 < 0) m0 += b / s; return {s, m0}; } }; using modint998244353 = StaticModint<998244353>; using modint1000000007 = StaticModint<1000000007>; using mint = modint998244353; int main(void) { ll t; cin >> t; while(t--) { ll n; cin >> n; if(n == 1) { cout << 1 << '\n'; continue; } cout << mint(2).pow(n * (n - 1) / 2) + (n - 1) * (mint(2).pow(n * (n - 1) / 2) - mint(3).pow(n - 2) * mint(2).pow(n * (n - 1) / 2 - 1 - 2 * (n - 2))) << '\n'; } }