結果

問題 No.1561 connect x connect
ユーザー shinchanshinchan
提出日時 2020-11-24 21:02:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 5,596 bytes
コンパイル時間 3,674 ms
コンパイル使用メモリ 258,048 KB
実行使用メモリ 739,024 KB
最終ジャッジ日時 2024-06-25 07:55:34
合計ジャッジ時間 7,323 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 6 ms
5,376 KB
testcase_02 MLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
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>> ret;
    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){
            ret.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 ret;
}

//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, n;
    cin >> n >> m;
    assert(n > 0 && n < 9 && m > 0 && m < 101);
    int ni = 1 << m;
    vector<vector<int>> ar(ni ,vector<int> (m));
    repp(i, ni, 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);
    repp(i, (m + 3) / 2, 1) col[i] = komo(i);
    vector<vector<int> > ans;
    rep(i, ni){
        int a = count(ar[i]);
        rep(j, col[a].size()){
            auto b = ar[i];
            ans.push_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.push_back(b);
    }
    //連結なpolyominoのindex
    vector<int> truepoly;
    rep(i, zen){
        bool ok = true;
        rep(j, m) if(ans[i][j] > 1) ok = false;
        if (ok) truepoly.pb(i);
    }
    auto kai = mnpoly(mnp, truepoly);
    ll polysum = 0LL;
    rep(i, n) (polysum += ll(n - i) * kai[i]) %= mod;
    cout << polysum << endl;
    return 0;
}
0