結果
問題 | No.1560 majority x majority |
ユーザー |
![]() |
提出日時 | 2021-03-31 00:10:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 2,083 bytes |
コンパイル時間 | 4,206 ms |
コンパイル使用メモリ | 261,352 KB |
最終ジャッジ日時 | 2025-01-20 00:58:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define rep(i,n) for (int i = 0; i < (n); ++i) #define repp(i,n,m) for (int i = m; i < (n); ++i) using namespace std; using namespace atcoder; using namespace internal; using ll = long long; using P = pair<int, int>; template <typename SE> void rev(vector<SE> &ar){reverse(ar.begin(),ar.end());} const int maxsize = 5000; using pbv = pair<bitset<maxsize>,vector<int>>; typedef bitset<maxsize> bset; int popcount(bset &a, int n){ int ans = 0; rep(i,n) if(a.test(i)) ans++; return ans; } int ten(vector<int> &a, int m){ rev(a); int ans = 0; rep(i,m){ ans += a[i]; if (i != m-1) ans *= 2; } return ans; } struct vs{ vector<int> to; vector<int> from; int cases; }; int main(){ bset bm(0); bm.set(); int n, m; cin >> n >> m; int rui = 1<<m; vector<vector<int>> ar(n,vector<int>(m)); rep(i,n) rep(j,m) cin >> ar[i][j]; vector<bset> b(m,0); rep(i,m){ rep(j,n){ if (ar[j][i] == 1) b[i].set(j); } } vector<int> popc(rui); queue<pbv> que; que.push(pbv(bm,{})); while (!que.empty()){ pbv p = que.front(); que.pop(); bset x = p.first; vector<int> c = p.second; int s = c.size(); if (s == m){ int pos = ten(c,m); int cnt = popcount(x,n); popc[pos] = cnt; } else { c.emplace_back(0); que.push(pbv(x,c)); c[s] = 1; x &= b[s]; que.push(pbv(x,c)); } } vector<vs> dp(rui); rep(i,rui) dp[i].cases = 0; rep(i,rui){ rep(j,m){ if (~i >> j & 1){ int t = i|1<<j; if (popc[t] * 2 < popc[i]) continue; dp[i].to.emplace_back(t); dp[t].from.emplace_back(i); } } } dp[0].cases = 1; repp(i,rui,1){ for (int x : dp[i].from){ dp[i].cases += dp[x].cases; } } cout << dp[rui-1].cases << endl; }