結果
問題 | No.2055 12x34... |
ユーザー | KKT89 |
提出日時 | 2024-01-29 10:06:09 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 3,393 bytes |
コンパイル時間 | 2,924 ms |
コンパイル使用メモリ | 226,172 KB |
実行使用メモリ | 30,948 KB |
最終ジャッジ日時 | 2024-01-29 10:06:20 |
合計ジャッジ時間 | 11,003 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
11,620 KB |
testcase_01 | AC | 17 ms
11,620 KB |
testcase_02 | AC | 21 ms
11,748 KB |
testcase_03 | AC | 28 ms
12,004 KB |
testcase_04 | AC | 34 ms
12,132 KB |
testcase_05 | AC | 34 ms
12,260 KB |
testcase_06 | AC | 33 ms
12,132 KB |
testcase_07 | AC | 29 ms
12,004 KB |
testcase_08 | AC | 26 ms
11,876 KB |
testcase_09 | AC | 36 ms
12,260 KB |
testcase_10 | AC | 39 ms
12,388 KB |
testcase_11 | AC | 25 ms
11,876 KB |
testcase_12 | AC | 128 ms
21,732 KB |
testcase_13 | AC | 225 ms
28,132 KB |
testcase_14 | AC | 85 ms
18,404 KB |
testcase_15 | AC | 89 ms
18,532 KB |
testcase_16 | AC | 247 ms
28,772 KB |
testcase_17 | AC | 81 ms
14,436 KB |
testcase_18 | AC | 153 ms
16,996 KB |
testcase_19 | AC | 37 ms
12,772 KB |
testcase_20 | AC | 23 ms
12,132 KB |
testcase_21 | AC | 37 ms
12,772 KB |
testcase_22 | AC | 203 ms
18,532 KB |
testcase_23 | AC | 214 ms
24,292 KB |
testcase_24 | AC | 146 ms
30,308 KB |
testcase_25 | AC | 205 ms
26,340 KB |
testcase_26 | AC | 184 ms
26,852 KB |
testcase_27 | AC | 156 ms
30,948 KB |
testcase_28 | AC | 167 ms
27,876 KB |
testcase_29 | AC | 223 ms
29,796 KB |
testcase_30 | AC | 195 ms
26,468 KB |
testcase_31 | AC | 176 ms
26,340 KB |
testcase_32 | AC | 170 ms
27,236 KB |
testcase_33 | AC | 128 ms
12,388 KB |
testcase_34 | AC | 103 ms
12,388 KB |
testcase_35 | AC | 103 ms
12,388 KB |
testcase_36 | AC | 104 ms
12,388 KB |
testcase_37 | AC | 110 ms
12,388 KB |
testcase_38 | AC | 102 ms
12,388 KB |
testcase_39 | AC | 104 ms
12,388 KB |
testcase_40 | AC | 104 ms
12,388 KB |
testcase_41 | AC | 103 ms
12,388 KB |
testcase_42 | AC | 103 ms
12,388 KB |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long int ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } template <int mod> struct static_modint { using mint = static_modint; int x; static_modint() : x(0) {} static_modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} mint &operator+=(const mint &rhs) { if ((x += rhs.x) >= mod) x -= mod; return *this; } mint &operator-=(const mint &rhs) { if ((x += mod - rhs.x) >= mod) x -= mod; return *this; } mint &operator*=(const mint &rhs) { x = (int)(1LL * x * rhs.x % mod); return *this; } mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); } mint pow(long long n) const { mint _x = *this, r = 1; while (n) { if (n & 1) r *= _x; _x *= _x; n >>= 1; } return r; } mint inv() const { return pow(mod - 2); } mint operator+() const { return *this; } mint operator-() const { return mint() - *this; } friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs.x == rhs.x; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs.x != rhs.x; } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; } friend istream &operator>>(istream &is, mint &a) { int64_t t; is >> t; a = static_modint<mod>(t); return (is); } }; const unsigned int mod = 998244353; using modint = static_modint<mod>; modint mod_pow(ll n, ll x) { return modint(n).pow(x); } modint mod_pow(modint n, ll x) { return n.pow(x); } template <typename T> struct Comination { vector<T> p, invp; Comination(int sz) : p(sz + 1), invp(sz + 1) { p[0] = 1; for (int i = 1; i <= sz; ++i) { p[i] = p[i - 1] * i; } invp[sz] = p[sz].inv(); for (int i = sz - 1; i >= 0; --i) { invp[i] = invp[i + 1] * (i + 1); } } T comb(int n, int r) { if (r < 0 or n < r) return 0; return p[n] * invp[n - r] * invp[r]; } T big_comb(T n, int r) { T res = invp[r]; for (int i = 0; i < r; ++i) { res *= (n - i); } return res; } }; using Comb = Comination<modint>; Comb p(1 << 20); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } map<int, modint> mp, dp; modint res = 0; for (int i = 0; i < n; i++) { { modint add = 0; if (mp.find(a[i] - 1) != mp.end()) add += mp[a[i] - 1]; if (dp.find(a[i] - 1) != dp.end()) add += dp[a[i] - 1]; res += add; dp[a[i]] += add; } mp[a[i]] += 1; } cout << res << endl; }