結果
問題 | No.1426 Got a Covered OR |
ユーザー | kwm_t |
提出日時 | 2021-03-13 12:49:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,607 bytes |
コンパイル時間 | 3,889 ms |
コンパイル使用メモリ | 235,152 KB |
実行使用メモリ | 6,416 KB |
最終ジャッジ日時 | 2024-10-15 05:12:48 |
合計ジャッジ時間 | 6,019 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
5,376 KB |
testcase_01 | AC | 5 ms
5,248 KB |
testcase_02 | AC | 5 ms
5,376 KB |
testcase_03 | AC | 5 ms
5,248 KB |
testcase_04 | AC | 5 ms
5,248 KB |
testcase_05 | AC | 5 ms
5,248 KB |
testcase_06 | AC | 5 ms
5,504 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,248 KB |
testcase_09 | AC | 6 ms
5,248 KB |
testcase_10 | AC | 5 ms
5,248 KB |
testcase_11 | AC | 5 ms
5,248 KB |
testcase_12 | AC | 23 ms
5,376 KB |
testcase_13 | AC | 25 ms
5,632 KB |
testcase_14 | AC | 21 ms
5,376 KB |
testcase_15 | AC | 21 ms
5,376 KB |
testcase_16 | AC | 8 ms
5,248 KB |
testcase_17 | AC | 11 ms
5,504 KB |
testcase_18 | AC | 43 ms
5,908 KB |
testcase_19 | AC | 43 ms
5,908 KB |
testcase_20 | AC | 20 ms
5,504 KB |
testcase_21 | AC | 28 ms
5,632 KB |
testcase_22 | AC | 39 ms
5,760 KB |
testcase_23 | AC | 70 ms
6,412 KB |
testcase_24 | AC | 72 ms
6,416 KB |
testcase_25 | AC | 60 ms
6,160 KB |
testcase_26 | AC | 59 ms
6,156 KB |
ソースコード
#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; using mint = modint1000000007; const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" struct combination { vector<mint> fact, ifact; combination(int n) :fact(n + 1), ifact(n + 1) { assert(n < mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i; } mint operator()(int n, int k) { return com(n, k); } mint com(int n, int k) { if (n < 0) return com(-n, k) * (k % 2 ? -1 : 1); if (k < 0 || k > n) return 0; return fact[n] * ifact[k] * ifact[n - k]; } mint inv(int n, int k) { if (n < 0) return inv(-n, k) * (k % 2 ? -1 : 1); if (k < 0 || k > n) return 0; return ifact[n] * fact[k] * fact[n - k]; } }c(200005); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int>B(N); rep(i, N) { cin >> B[i]; } vector<pair<int, int>>subB; subB.push_back({ 0,0 }); rep(i, N) { if (-1 == B[i]) { continue; } subB.push_back({ B[i],i + 1 }); } mint ans = 1; vector<mint>pow2(100005); rep(i, N + 1) { if (0 == i) { pow2[i] = 1; } else { pow2[i] = pow2[i - 1] * 2; } } rep(i, subB.size() - 1) { auto bef = subB[i]; auto aft = subB[i + 1]; mint anssub = 0; rep(j, aft.second - bef.second + 1) { //★★ mint anssubsub = c(aft.second - bef.second, j); vector<int>pat(4, 0); rep(k, 30) { int x = 1 & (bef.first >> k); int y = 1 & (aft.first >> k); if ((1 == x) && (0 == y)) { pat[0]++; } else if ((0 == x) && (1 == y)) { pat[1]++; } else if ((0 == x) && (0 == y)) { pat[2]++; } else {//11 pat[3]++; } } rep(k, 4) { rep(l, pat[k]) { if (0 == k) { anssubsub *= 0; } else if (1 == k) { anssubsub *= pow2[aft.second - bef.second - j] - 1; } else if (2 == k) { anssubsub *= 1; } else { anssubsub *= pow2[aft.second - bef.second - j]; } } } if (0 == j % 2) { anssub += anssubsub; } else { anssub -= anssubsub; } } ans *= anssub; } cout << ans.val() << endl; return 0; }