結果
問題 |
No.1426 Got a Covered OR
|
ユーザー |
|
提出日時 | 2021-04-17 17:19:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 394 ms / 2,000 ms |
コード長 | 1,778 bytes |
コンパイル時間 | 2,500 ms |
コンパイル使用メモリ | 198,620 KB |
最終ジャッジ日時 | 2025-01-20 21:24:42 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; long long comb[32][32]; void init() { for (int i = 0; i < 32; i++) { comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } long long modpow(long long x, long long p, long long mod) { long long ret = 1; while (p) { if (p & 1) ret = ret * x % mod; x = x * x % mod; p >>= 1; } return ret; } long long calc(int x, int y, int n) { vector<long long> cur(32); cur[x] = 1; for (int i = 0; i < n; i++) { vector<long long> nxt(32); // xで立っているbitがall zeroのとき for (int j = x; j <= y; j++) { for (int k = 1; k <= y-j; k++) { nxt[j+k] += cur[j] * comb[y-j][k] % MOD; nxt[j+k] %= MOD; } } // xで立っているbitがall zeroではないとき for (int j = x; j <= y; j++) { long long base = modpow(2, j, MOD) - 1; if (base < 0) base += MOD; base = base * cur[j] % MOD; for (int k = 0; k <= y-j; k++) { nxt[j+k] += base * comb[y-j][k] % MOD; nxt[j+k] %= MOD; } } cur = nxt; } return cur[y]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); init(); int n; cin >> n; vector<int> b(n); vector<int> p; for (int i = 0; i < n; i++) { cin >> b[i]; if (b[i] != -1) p.push_back(i); } long long ret = 1; int j = -1; int x = 0; for (int i: p) { int y = b[i]; if ((y & x) != x) { ret = 0; break; } int bx = __builtin_popcountll(x); int by = __builtin_popcountll(y); ret *= calc(bx, by, i-j); ret %= MOD; x = y; j = i; } cout << ret << endl; return 0; }