結果

問題 No.1561 connect x connect
コンテスト
ユーザー noya2
提出日時 2020-11-22 14:04:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,894 bytes
コンパイル時間 3,807 ms
コンパイル使用メモリ 245,368 KB
最終ジャッジ日時 2025-01-16 04:21:32
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 17 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#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 ll = long long;
using ld = long double;
using P = pair<int, int>;
using PI = pair<pair<int,int>,int>;
using PL = pair<long long, long long>;
using PLL = pair<pair<long long, long long>, long long>;
using Pxy = pair<long double, long double>;
using Tiib = tuple<int, int, bool>;
using vvl = vector<vector<ll>>;
const int INF = 1001001007;
const int modd = 1000000007;
const long long modl = 1000000007LL;
const long long mod = 998244353LL;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

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)];}
};

//bit列の島の数
int num(vector<int> a){
    a.emplace_back(0);
    int n = a.size();
    int ans = 0;
    int ima = 0;
    rep(i,n){
        if (a[i] == 0){
            if (ima == 1) ans++; 
            ima = 0;
        }
        else {
            ima = 1;
        }
    }
    return ans;
}

//bit列の島を色塗りする
vector<int> nul(vector<int> &a, vector<int> &b){
    vector<int> ans(a.size());
    int ima = 0;
    int cnt = 0;
    rep(i,a.size()){
        if (a[i] == 0){
            ans[i] = 0;
            if (ima == 1) cnt++;
            ima = 0;
        }
        else {
            ans[i] = b[cnt];
            ima = 1;
        }
    }
    return ans;
}

//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 == num(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 = num(ar[i]);
        rep(j,col[a].size()){
            auto b = ar[i];
            ans.emplace_back(nul(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 = 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の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 %= modl;
    }
    cout << polysum << endl;
}
0