結果
問題 | No.1741 Arrays and XOR Procedure |
ユーザー | okuraofvegetabl |
提出日時 | 2021-11-12 23:45:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 4,273 bytes |
コンパイル時間 | 2,947 ms |
コンパイル使用メモリ | 206,224 KB |
実行使用メモリ | 14,912 KB |
最終ジャッジ日時 | 2023-08-17 04:37:33 |
合計ジャッジ時間 | 4,647 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 38 ms
14,912 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 32 ms
14,808 KB |
testcase_06 | AC | 38 ms
14,800 KB |
testcase_07 | AC | 40 ms
14,776 KB |
testcase_08 | AC | 33 ms
14,788 KB |
testcase_09 | AC | 33 ms
13,184 KB |
testcase_10 | AC | 35 ms
13,472 KB |
testcase_11 | AC | 28 ms
11,088 KB |
testcase_12 | AC | 22 ms
9,356 KB |
testcase_13 | AC | 34 ms
13,028 KB |
testcase_14 | AC | 25 ms
10,156 KB |
testcase_15 | AC | 30 ms
12,424 KB |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 12 ms
6,448 KB |
testcase_18 | AC | 25 ms
10,412 KB |
testcase_19 | AC | 3 ms
4,380 KB |
testcase_20 | AC | 36 ms
14,652 KB |
testcase_21 | AC | 28 ms
11,688 KB |
testcase_22 | AC | 26 ms
10,912 KB |
testcase_23 | AC | 11 ms
6,128 KB |
testcase_24 | AC | 4 ms
4,380 KB |
testcase_25 | AC | 36 ms
14,308 KB |
testcase_26 | AC | 16 ms
7,796 KB |
testcase_27 | AC | 3 ms
4,376 KB |
testcase_28 | AC | 28 ms
11,548 KB |
testcase_29 | AC | 31 ms
12,504 KB |
testcase_30 | AC | 27 ms
11,260 KB |
testcase_31 | AC | 3 ms
4,380 KB |
testcase_32 | AC | 17 ms
7,732 KB |
testcase_33 | AC | 21 ms
8,776 KB |
testcase_34 | AC | 8 ms
5,112 KB |
testcase_35 | AC | 2 ms
4,376 KB |
testcase_36 | AC | 5 ms
4,376 KB |
testcase_37 | AC | 16 ms
7,468 KB |
testcase_38 | AC | 35 ms
13,940 KB |
testcase_39 | AC | 15 ms
6,916 KB |
testcase_40 | AC | 2 ms
4,376 KB |
testcase_41 | AC | 8 ms
4,868 KB |
testcase_42 | AC | 3 ms
4,380 KB |
testcase_43 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define eps 1e-9 #define INF 2000000000 // 2e9 #define LLINF 2000000000000000000ll // 2e18 (llmax:9e18) #define all(x) (x).begin(), (x).end() #define sq(x) ((x) * (x)) #define rep(i, x) for (int i = 0; i < (int)(x); i++) #define drep(i, x) for (int i = ((int)(x)-1); i >= 0; i--) #define popcount __builtin_popcount #define next __next #define prev __prev #ifndef LOCAL #define dmp(...) ; #else #define dmp(...) \ cerr << "[ " << #__VA_ARGS__ << " ] : " << dump_str(__VA_ARGS__) << endl #endif // ---------------- Utility ------------------ template <class T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <class T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template <class T> using MaxHeap = priority_queue<T>; template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>; template <class T> vector<T> vect(int len, T elem) { return vector<T>(len, elem); } // ----------------- Input ------------------- template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; } template <class T> istream &operator>>(istream &is, vector<T> &vec) { for (int i = 0; i < vec.size(); i++) is >> vec[i]; return is; } // ----------------- Output ------------------ template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << p.first << ',' << p.second; } template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &e : v) os << e << " "; return os; } template <class T> ostream &operator<<(ostream &os, const deque<T> &d) { for (const T &e : d) os << e << " "; return os; } template <class T> ostream &operator<<(ostream &os, const set<T> &s) { os << "{ "; for (const T &e : s) os << e << " "; return os << "}"; } template <class T, class U> ostream &operator<<(ostream &os, const map<T, U> &m) { os << "{ "; for (const auto &[key, val] : m) os << "( " << key << " -> " << val << " ) "; return os << "}"; } template <class TupleTy, size_t... I> void dump_tuple(ostream &os, const TupleTy t, std::index_sequence<I...>) { (..., (os << (I == 0 ? "" : ",") << std::get<I>(t))); } template <class... Args> ostream &operator<<(ostream &os, const tuple<Args...> &t) { os << "("; dump_tuple(os, t, std::make_index_sequence<sizeof...(Args)>()); return os << ")"; } void dump_str_rec(ostringstream &) {} template <class Head, class... Tail> void dump_str_rec(ostringstream &oss, Head &&head, Tail &&... tail) { oss << ", " << head; dump_str_rec(oss, forward<Tail>(tail)...); } template <class T, class... U> string dump_str(T &&arg, U &&... args) { ostringstream oss; oss << arg; dump_str_rec(oss, forward<U>(args)...); return oss.str(); } // --------------- Fast I/O ------------------ void fastio() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); } // ------------------ ACL -------------------- #include <atcoder/modint> constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; using mint = atcoder::static_modint<MOD>; ostream &operator<<(ostream &os, const mint &v) { return os << v.val(); } // ------------ End of template -------------- #define endl "\n" using ll = long long; using pii = pair<int, int>; const bool multitest = false; int nCk(int n, int k) { assert(n >= 1 && k >= 0 && k <= n); while (n > 0) { int nb = (n & 1), kb = (k & 1); n >>= 1; k >>= 1; if (nb < kb) return 0; } return 1; } void solve() { int N; cin >> N; vector<int> B(N); cin >> B; auto dp = vect(N + 1, vect(2, mint(0))); dp[0][0] = mint(1); for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { if (B[i] == -1 || B[i] == k) { dp[i + 1][(j + k * nCk(N - 1, i)) % 2] += dp[i][j]; } } } } cout << dp[N][1] << endl; return; } int main() { fastio(); if (!multitest) { solve(); } else { cerr << "[Warning] Multi testcase mode on" << endl; int t; cin >> t; while (t--) solve(); } return 0; }