結果
問題 | No.1304 あなたは基本が何か知っていますか?私は知っています. |
ユーザー | risujiroh |
提出日時 | 2020-12-01 01:55:19 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 4,663 bytes |
コンパイル時間 | 2,469 ms |
コンパイル使用メモリ | 205,572 KB |
実行使用メモリ | 15,868 KB |
最終ジャッジ日時 | 2023-09-03 03:09:01 |
合計ジャッジ時間 | 36,493 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
15,544 KB |
testcase_01 | AC | 20 ms
14,868 KB |
testcase_02 | AC | 11 ms
15,680 KB |
testcase_03 | AC | 134 ms
14,524 KB |
testcase_04 | AC | 16 ms
15,560 KB |
testcase_05 | AC | 15 ms
14,348 KB |
testcase_06 | AC | 13 ms
15,620 KB |
testcase_07 | AC | 16 ms
14,472 KB |
testcase_08 | AC | 34 ms
15,868 KB |
testcase_09 | AC | 16 ms
14,344 KB |
testcase_10 | AC | 14 ms
15,624 KB |
testcase_11 | AC | 15 ms
14,684 KB |
testcase_12 | AC | 15 ms
14,412 KB |
testcase_13 | AC | 15 ms
15,620 KB |
testcase_14 | AC | 15 ms
15,556 KB |
testcase_15 | AC | 15 ms
14,352 KB |
testcase_16 | AC | 16 ms
14,476 KB |
testcase_17 | AC | 26 ms
11,336 KB |
testcase_18 | AC | 15 ms
11,192 KB |
testcase_19 | AC | 16 ms
11,168 KB |
testcase_20 | AC | 13 ms
11,196 KB |
testcase_21 | AC | 26 ms
11,404 KB |
testcase_22 | AC | 15 ms
11,208 KB |
testcase_23 | AC | 15 ms
11,232 KB |
testcase_24 | AC | 16 ms
11,300 KB |
testcase_25 | AC | 56 ms
11,448 KB |
testcase_26 | AC | 32 ms
11,348 KB |
testcase_27 | AC | 35 ms
11,336 KB |
testcase_28 | AC | 39 ms
11,384 KB |
testcase_29 | AC | 33 ms
11,388 KB |
testcase_30 | AC | 45 ms
11,412 KB |
testcase_31 | AC | 71 ms
11,368 KB |
testcase_32 | AC | 33 ms
11,436 KB |
testcase_33 | AC | 56 ms
11,412 KB |
testcase_34 | AC | 34 ms
11,416 KB |
testcase_35 | AC | 48 ms
11,436 KB |
testcase_36 | AC | 64 ms
11,444 KB |
testcase_37 | AC | 48 ms
11,400 KB |
testcase_38 | AC | 45 ms
11,372 KB |
testcase_39 | AC | 79 ms
11,444 KB |
testcase_40 | AC | 49 ms
11,412 KB |
testcase_41 | AC | 80 ms
11,340 KB |
testcase_42 | AC | 49 ms
11,368 KB |
testcase_43 | AC | 48 ms
11,340 KB |
testcase_44 | AC | 65 ms
11,364 KB |
04_evil_A_01 | RE | - |
04_evil_A_02 | RE | - |
04_evil_A_03 | RE | - |
04_evil_A_04 | RE | - |
04_evil_A_05 | RE | - |
04_evil_A_06 | RE | - |
04_evil_A_07 | RE | - |
04_evil_A_08 | RE | - |
04_evil_A_09 | RE | - |
04_evil_A_10 | RE | - |
05_evil_B_01 | RE | - |
05_evil_B_02 | RE | - |
05_evil_B_03 | RE | - |
05_evil_B_04 | RE | - |
05_evil_B_05 | RE | - |
05_evil_B_06 | RE | - |
05_evil_B_07 | RE | - |
05_evil_B_08 | RE | - |
05_evil_B_09 | RE | - |
05_evil_B_10 | RE | - |
06_evil_C_01 | TLE | - |
06_evil_C_02 | TLE | - |
06_evil_C_03 | TLE | - |
06_evil_C_04 | TLE | - |
06_evil_C_05 | TLE | - |
06_evil_C_06 | TLE | - |
06_evil_C_07 | TLE | - |
06_evil_C_08 | TLE | - |
06_evil_C_09 | TLE | - |
06_evil_C_10 | AC | 5 ms
10,468 KB |
ソースコード
#include <bits/stdc++.h> template <uint32_t Modulus> class ModularInt { using M = ModularInt; public: static_assert(int(Modulus) >= 1, "Modulus must be in the range [1, 2^31)"); static constexpr int modulus() { return Modulus; } static M raw(uint32_t v) { return *reinterpret_cast<M*>(&v); } ModularInt() : v_(0) {} ModularInt(int64_t v) : v_((v %= Modulus) < 0 ? v + Modulus : v) {} template <class T> explicit operator T() const { return v_; } M& operator++() { return v_ = ++v_ == Modulus ? 0 : v_, *this; } M& operator--() { return --(v_ ? v_ : v_ = Modulus), *this; } M operator+() const { return *this; } M operator-() const { return raw(v_ ? Modulus - v_ : 0); } M& operator*=(M o) { return v_ = uint64_t(v_) * o.v_ % Modulus, *this; } M& operator/=(M o) { auto [inv, gcd] = extgcd(o.v_, Modulus); assert(gcd == 1); return *this *= inv; } M& operator+=(M o) { return v_ = int(v_ += o.v_ - Modulus) < 0 ? v_ + Modulus : v_, *this; } M& operator-=(M o) { return v_ = int(v_ -= o.v_) < 0 ? v_ + Modulus : v_, *this; } friend M operator++(M& a, int) { return std::exchange(a, ++M(a)); } friend M operator--(M& a, int) { return std::exchange(a, --M(a)); } friend M operator*(M a, M b) { return a *= b; } friend M operator/(M a, M b) { return a /= b; } friend M operator+(M a, M b) { return a += b; } friend M operator-(M a, M b) { return a -= b; } friend std::istream& operator>>(std::istream& is, M& x) { int64_t v; return is >> v, x = v, is; } friend std::ostream& operator<<(std::ostream& os, M x) { return os << x.v_; } friend bool operator==(M a, M b) { return a.v_ == b.v_; } friend bool operator!=(M a, M b) { return a.v_ != b.v_; } private: static std::array<int, 2> extgcd(int a, int b) { std::array x{1, 0}; while (b) std::swap(x[0] -= a / b * x[1], x[1]), std::swap(a %= b, b); return {x[0], a}; } uint32_t v_; }; template <class T> constexpr T power(T a, int64_t n) { assert(n >= 0); T res = n & 1 ? a : 1; while (n >>= 1) { a *= a; if (n & 1) res *= a; } return res; } #pragma region my_template struct Rep { struct I { int i; void operator++() { ++i; } int operator*() const { return i; } bool operator!=(I o) const { return i < *o; } }; const int l_, r_; Rep(int l, int r) : l_(l), r_(r) {} Rep(int n) : Rep(0, n) {} I begin() const { return {l_}; } I end() const { return {r_}; } }; struct Per { struct I { int i; void operator++() { --i; } int operator*() const { return i; } bool operator!=(I o) const { return i > *o; } }; const int l_, r_; Per(int l, int r) : l_(l), r_(r) {} Per(int n) : Per(0, n) {} I begin() const { return {r_ - 1}; } I end() const { return {l_ - 1}; } }; template <class F> struct Fix : private F { Fix(F f) : F(f) {} template <class... Args> decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class T = int> T scan() { T res; std::cin >> res; return res; } template <class T, class U = T> bool chmin(T& a, U&& b) { return b < a ? a = std::forward<U>(b), true : false; } template <class T, class U = T> bool chmax(T& a, U&& b) { return a < b ? a = std::forward<U>(b), true : false; } #ifndef LOCAL #define DUMP(...) void(0) template <int OnlineJudge, int Local> constexpr int OjLocal = OnlineJudge; #endif using namespace std; #define ALL(c) begin(c), end(c) #pragma endregion using Mint = ModularInt<998244353>; constexpr int L = OjLocal<10, 4>; int main() { cin.tie(nullptr)->sync_with_stdio(false); cout << fixed << setprecision(20); int n = scan(); int k = scan(); int l = scan(); int r = scan(); chmin(l, ~-(1 << L)); chmin(r, ~-(1 << L)); bitset<1 << L> bs; while (k--) bs[scan()] = 1; vector dp(1 << L, vector<Mint>(1 << L)); for (int i : Rep(1 << L)) if (bs[i]) dp[i][i] = 1; for (int _ = n - 1; _--;) { vector ndp(1 << L, vector<Mint>(1 << L)); for (int x : Rep(1 << L)) { Mint sum = accumulate(ALL(dp[x]), Mint{}); for (int i : Rep(1 << L)) if (bs[i]) ndp[x ^ i][i] += sum - dp[x][i]; // for (int y : Rep(1 << L)) // for (int i : Rep(1 << L)) // if (bs[i] and i != y) ndp[x ^ i][i] += dp[x][y]; } dp = move(ndp); DUMP(dp); } Mint ans; for (int i : Rep(l, r + 1)) ans += accumulate(ALL(dp[i]), Mint(0)); cout << ans << '\n'; }