結果

問題 No.1561 connect x connect
ユーザー shinchanshinchan
提出日時 2020-11-23 11:57:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,680 bytes
コンパイル時間 3,645 ms
コンパイル使用メモリ 258,580 KB
実行使用メモリ 27,296 KB
最終ジャッジ日時 2024-06-25 07:53:42
合計ジャッジ時間 8,010 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,624 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 58 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 10 ms
5,376 KB
testcase_13 AC 51 ms
5,376 KB
testcase_14 AC 176 ms
9,088 KB
testcase_15 AC 415 ms
9,600 KB
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 mod=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 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> color(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;
};

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 (auto itr = q.s.begin(); itr != q.s.end(); itr++){
            dat p = q;
            int m = *itr;
            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> v){
    int ma = 0, n = v.size();
    for(auto& i : v){
        ma = max(ma, i);
        if(i) i = 1;
    }
    return ma == count(v);
}

vector<ll> next(vector<vector<ll>> &mat, vector<ll> &ima){
    int n = ima.size();
    vector<ll> ret(n, 0LL);
    rep(i, n) rep(j, n) (ret[i] += mat[i][j] * ima[j]) %= mod;
    return ret;
}

vector<ll> mnpoly(vector<vector<ll>> &mnp, vector<int> &truepoly){
    int n = mnp.size(), m = truepoly.size();
    vector<ll> ret(n, 0LL);
    rep(i, n) for(int j: truepoly) ret[i] += mnp[i][j];
    return ret;
}

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 formulas
    int zen = ans.size();
    map<vector<int>,int> mp;
    rep(i,zen) mp[ans[i]] = i;
    //recurrence matrix
    vector<vector<ll> > mat(zen,vector<ll> (zen,0LL));
    vector<int> tan(m, 0);
    rep(i,zen){
        repp(j,ni,1){
            auto x = color(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 = next(mat, a);
        mnp.emplace_back(b);
    }
    //連結なpolyominoのindex
    vector<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 %= mod;
    }
    cout << polysum << endl;
}
0