結果
| 問題 | No.1561 connect x connect |
| ユーザー |
 shinchan
|
| 提出日時 | 2020-11-23 11:14:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,812 bytes |
| コンパイル時間 | 4,257 ms |
| コンパイル使用メモリ | 246,232 KB |
| 最終ジャッジ日時 | 2025-01-16 04:53:53 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 TLE * 18 MLE * 3 |
ソースコード
#include <bits/stdc++.h>#define be(v) (v).begin(),(v).end()#define pb(q) push_back(q)typedef long long ll;using namespace std;const ll modl=1000000007, INF=(1LL<<60);#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;#define rep(i,n) for (int i = 0; i < (n); ++i)#define repp(i,n,m) for (int i = m; i < (n); ++i)/*struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}mint operator+(const mint a) const { return mint(*this) += a;}mint operator-(const mint a) const { return mint(*this) -= a;}mint operator*(const mint a) const { return mint(*this) *= a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const { return pow(mod-2);}mint& operator/=(const mint a) { return *this *= a.inv();}mint operator/(const mint a) const { return mint(*this) /= a;}};*/struct UnionFind {vector<int> d;UnionFind(int n=0): d(n,-1) {}int find(int x) {if (d[x] < 0) return x;return d[x] = find(d[x]);}bool unite(int x, int y) {x = find(x); y = find(y);if (x == y) return false;if (d[x] > d[y]) swap(x,y);d[x] += d[y];d[y] = x;return true;}bool same(int x, int y) { return find(x) == find(y);}int size(int x) { return -d[find(x)];}};int count(vector<int> v){v.pb(0);int ret = 0;bool f = false;for(int i : v){if(i) f = true;else if(f) ret++, f = false;}return ret;}vector<int> paint(vector<int> &a, vector<int> &b){int id = 0, n = a.size();vector<int> ret(n, 0);bool f = false;for(int i=0;i<n;i++){if(a[i]) ret[i] = b[id], f = true;else if(f) id++, f = false;}return ret;}//aとbを接続したときの新たな右端の色vector<int> iro(vector<int> &a, vector<int> &b){int n = a.size();vector<int> ans(n,0);int ma = 0;rep(i,n) ma = max(ma,a[i]);vector<vector<int>> ar(ma,vector<int>(0));vector<bool> ok(ma,false);rep(i,n){if (a[i] != 0){if (b[i] == 1) ok[a[i]-1] = true;ar[a[i]-1].emplace_back(i);}}rep(i,ma) if (!ok[i]) return ans;UnionFind tree(n);repp(i,n,1){if (b[i-1] == 1 && b[i] == 1) tree.unite(i-1,i);}rep(i,ma){auto &r = ar[i];repp(j,r.size(),1) tree.unite(r[0],r[j]);}int ima = 1;map<int,int> mp;rep(i,n){if (b[i] == 0) ans[i] = 0;else {int ne = tree.find(i);if (mp.find(ne) == mp.end()){mp[ne] = ima;ans[i] = ima;ima++;}else {ans[i] = mp[ne];}}}return ans;}struct dat{set<int> s;stack<int> st;vector<int> an;set<int> stin;int ima;};set<int> ::iterator ite;;vector<vector<int>> komo(int n){vector<vector<int>> ans(0,vector<int>(n));queue<dat> que;dat a; a.ima = 2; a.s.insert(1); que.push(a);while (!que.empty()){dat q = que.front(); que.pop();if (q.an.size() == n){ans.emplace_back(q.an);continue;}for (ite = q.s.begin(); ite != q.s.end(); ite++){dat p = q;int m = *ite;if (p.stin.find(m) == p.stin.end()){p.an.emplace_back(m);p.stin.insert(m);p.st.push(m);if (m == p.ima -1){p.s.insert(p.ima);p.ima++;}}else {p.an.emplace_back(m);int col = p.st.top();while (col != m){p.s.erase(col);p.st.pop();col = p.st.top();}}que.push(p);}}return ans;}//S_(m,1) としてありえるかbool chan(vector<int> &a){int ma = 0;vector<int> si = a;rep(i,a.size()) {ma = max(ma,a[i]);if (a[i] == 0) si[i] = 0;else si[i] = 1;}return ma == count(si);}vector<ll> tugi(vector<vector<ll>> &mat, vector<ll> ima){vector<ll> ans(ima.size(),0LL);rep(i,ima.size()){rep(j,ima.size()){ans[i] += mat[i][j] * ima[j];ans[i] %= modl;}}return ans;}vector<ll> mnpoly(vector<vector<ll>> &mnp, vector<int> &truepoly){vector<ll> ans(mnp.size(),0LL);rep(i,mnp.size()){rep(j,truepoly.size()){ans[i] += mnp[i][truepoly[j]];}}return ans;}int main() {int m; cin >> m;int n; cin >> n;int ni = 1<<m;vector<vector<int>> ar(1<<m,vector<int>(m));repp(i,1<<m,1){rep(j,m){if (i >> j & 1) ar[i][j] = 1;else ar[i][j] = 0;}}vector<vector<vector<int>>> col((m+3)/2,vector<vector<int>>(0,vector<int>(0)));repp(i,(m+3)/2,1){col[i] = komo(i);}vector<vector<int>> ans;rep(i,ar.size()){int a = count(ar[i]);rep(j,col[a].size()){auto b = ar[i];ans.emplace_back(paint(b,col[a][j]));}}//the number of recurrence formulasint zen = ans.size();map<vector<int>,int> mp;rep(i,zen){mp[ans[i]] = i;}//recurrence matrixvector<vector<ll>> mat(zen,vector<ll>(zen,0LL));vector<int> tan(m,0);rep(i,zen){repp(j,ni,1){auto x = iro(ans[i],ar[j]);if (x == tan) continue;int ind = mp[x];mat[ind][i] += 1LL;}}vector<vector<ll>> mnp(1,vector<ll>(zen));rep(i,zen){if (chan(ans[i])) mnp[0][i] = 1LL;else mnp[0][i] = 0LL;}rep(i,n){auto a = mnp[i];auto b = tugi(mat,a);mnp.emplace_back(b);}//連結なpolyominoのindexvector<int> truepoly;rep(i,zen){bool t = true;rep(j,m){if (ans[i][j] > 1) t = false;}if (t) truepoly.emplace_back(i);}auto kai = mnpoly(mnp,truepoly);ll polysum = 0LL;rep(i,n) {polysum += ll(n-i) * kai[i];polysum %= modl;}cout << polysum << endl;}