Submission #62274
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 | #include "bits/stdc++.h" #pragma GCC optimize("Ofast") /** * author: r1933 * created: 2020-08-15T12:11:09 */ // Begin Header {{{ using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) x.begin(), x.end() #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) constexpr size_t operator "" _zu(unsigned long long value) { return value; }; constexpr intmax_t operator "" _jd(unsigned long long value) { return value; }; constexpr uintmax_t operator "" _ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template < class T, class Compare = less<>> using MaxHeap = priority_queue<T, vector<T>, Compare>; template < class T, class Compare = greater<>> using MinHeap = priority_queue<T, vector<T>, Compare>; inline void input() {} template < class Head, class ... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template < class T> inline istream& operator>>(istream &is, vector<T> &vec) { for (auto &e: vec) { is >> e; } return is; } inline void output() { cout << "\n" ; } template < class Head, class ... Tail> inline void output(Head&& head, Tail&&... tail) { cout << head; if ( sizeof ...(tail)) { cout << " " ; } output(forward<Tail>(tail)...); } template < class T> inline ostream& operator<<(ostream &os, const vector<T> &vec) { static constexpr const char *delim[] = { " " , "" }; for ( const auto &e: vec) { os << e << delim[&e == &vec.back()]; } return os; } template < class T> inline vector<T> makeVector( const T &initValue, size_t sz) { return vector<T>(sz, initValue); } template < class T, class ... Args> inline auto makeVector( const T &initValue, size_t sz, Args... args) { return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...)); } template < class Func> class FixPoint : Func { public : explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template < class ... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(* this , std::forward<Args>(args)...); } }; template < class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template < class Container> struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template < class Container> auto reversed(Container &c) { return reverse_t<Container>(c); } template < class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true ); } template < class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true ); } template < class T> inline T diff( const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } // End Header }}} const intmax_t MOD = 998244353; // ModInt {{{ template <intmax_t MOD> class ModInt { intmax_t value; public : inline ModInt( const ModInt& other) : value(other.value) {} inline ModInt(intmax_t value = 0) { if (value >= MOD) { this ->value = value % MOD; } else if (value < 0) { this ->value = (value % MOD + MOD) % MOD; } else { this ->value = value; } } template < class T> explicit inline operator T() const { return static_cast <T>(value); } inline ModInt inverse() const { return ModInt:: pow (value, MOD - 2); } inline ModInt& operator+=( const ModInt other) { if ((value += other.value) >= MOD) value -= MOD; return * this ; } inline ModInt& operator-=( const ModInt other) { if ((value -= other.value) < 0) value += MOD; return * this ; } inline ModInt& operator*=( const ModInt other) { value = (value * other.value) % MOD; return * this ; } inline ModInt& operator/=( const ModInt other) { value = (value * other.inverse().value) % MOD; return * this ; } inline ModInt operator+( const ModInt other) { return ModInt(* this ) += other; } inline ModInt operator-( const ModInt other) { return ModInt(* this ) -= other; } inline ModInt operator*( const ModInt other) { return ModInt(* this ) *= other; } inline ModInt operator/( const ModInt other) { return ModInt(* this ) /= other; } inline bool operator==( const ModInt other) { return value == other.value; } inline bool operator!=( const ModInt other) { return value != other.value; } friend ostream& operator<<(ostream &os, const ModInt other) { os << other.value; return os; } friend istream& operator>>(istream &is, ModInt& other) { is >> other.value; return is; } static constexpr inline ModInt pow (intmax_t n, intmax_t p) { intmax_t ret = 1; for (; p > 0; p >>= 1) { if (p & 1) ret = (ret * n) % MOD; n = (n * n) % MOD; } return ret; } }; using Mint = ModInt<MOD>; // }}} signed main() { ios_base::sync_with_stdio( false ); cin.tie(nullptr); cout.setf(ios_base::fixed); cout.precision(10); var( size_t , N); assert (1 <= N && N <= 5'000); vector<intmax_t> a(N); input(a); vector<Mint> pow2( size_t (1e6) + 1); for ( const auto ai: a) { assert (1 <= ai && ai <= 1 '000' 000); pow2[ai] = Mint:: pow (2, ai); } auto dp = makeVector<Mint>(0, 2, N + 1); // dp[i][j] := 色 1...i で、色の種類数が j となるようなボールの選び方の総数 (i は偶奇のみ保持) // dp[0][j] := 最新の偶数インデックスにおける値 // dp[1][j] := 最新の奇数インデックスにおける値 dp[0][0] = 1; reps(i, 1, N) { reps(j, 0, i) { if (j == 0) { dp[i & 1][j] += dp[(i - 1) & 1][j]; } else { dp[i & 1][j] += dp[(i - 1) & 1][j] + dp[(i - 1) & 1][j - 1] * Mint(pow2[a[i - 1]] - Mint(1)); } } if (i != N) reps(j, 0, i) dp[(i + 1) & 1][j] = 0; } vector<Mint> cumsum(N + 1); reps(j, 1, N) { cumsum[j] = cumsum[j - 1] + dp[N & 1][j]; } var( size_t , Q); assert (1 <= Q && Q <= 1 '000' 000); while (Q--) { var(intmax_t, L, R); assert (1 <= L && L <= R && R <= N); output(cumsum[R] - cumsum[L - 1]); } return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 1351 - Colorful Balls |
ユーザー名 | もけ |
投稿日時 | 2020-08-15 12:39:26 |
言語 | C++17 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 7152 Byte |
最大実行時間 | 205 ms |
最大メモリ使用量 | 72392 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
input01 | AC | 26 ms | 8408 KB |
1
|
input02 | AC | 25 ms | 8228 KB |
1
|
input03 | AC | 22 ms | 8308 KB |
1
|
input04 | AC | 25 ms | 8256 KB |
1
|
input05 | AC | 21 ms | 8336 KB |
1
|
input06 | AC | 24 ms | 8408 KB |
1
|
input07 | AC | 24 ms | 8356 KB |
1
|
input08 | AC | 22 ms | 8300 KB |
1
|
input09 | AC | 25 ms | 8368 KB |
1
|
input10 | AC | 22 ms | 8536 KB |
1
|
input11 | AC | 52 ms | 10384 KB |
1
|
input12 | AC | 123 ms | 17356 KB |
1
|
input13 | AC | 130 ms | 23428 KB |
1
|
input14 | AC | 109 ms | 27100 KB |
1
|
input15 | AC | 36 ms | 27524 KB |
1
|
input16 | AC | 91 ms | 29312 KB |
1
|
input17 | AC | 180 ms | 37416 KB |
1
|
input18 | AC | 205 ms | 47060 KB |
1
|
input19 | AC | 191 ms | 56696 KB |
1
|
input20 | AC | 156 ms | 65344 KB |
1
|
input21 | AC | 74 ms | 66820 KB |
1
|
input22 | AC | 62 ms | 66984 KB |
1
|
input23 | AC | 108 ms | 72392 KB |
1
|
input_sample01 | AC | 20 ms | 72284 KB |
1
|
input_sample02 | AC | 22 ms | 72356 KB |
1
|