結果

問題 No.578 3 x N グリッド上のサイクルのサイズ(easy)
ユーザー HIR180HIR180
提出日時 2020-04-22 01:20:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,545 bytes
コンパイル時間 3,115 ms
コンパイル使用メモリ 227,228 KB
実行使用メモリ 9,792 KB
最終ジャッジ日時 2023-07-30 21:58:16
合計ジャッジ時間 5,715 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,464 KB
testcase_01 AC 3 ms
9,600 KB
testcase_02 AC 3 ms
9,496 KB
testcase_03 AC 3 ms
9,608 KB
testcase_04 AC 3 ms
9,492 KB
testcase_05 AC 3 ms
9,652 KB
testcase_06 AC 3 ms
9,556 KB
testcase_07 AC 3 ms
9,572 KB
testcase_08 AC 3 ms
9,476 KB
testcase_09 AC 3 ms
9,476 KB
testcase_10 AC 3 ms
9,572 KB
testcase_11 AC 3 ms
9,480 KB
testcase_12 AC 3 ms
9,780 KB
testcase_13 AC 3 ms
9,528 KB
testcase_14 AC 3 ms
9,532 KB
testcase_15 AC 3 ms
9,536 KB
testcase_16 AC 3 ms
9,528 KB
testcase_17 AC 3 ms
9,580 KB
testcase_18 AC 3 ms
9,476 KB
testcase_19 AC 3 ms
9,736 KB
testcase_20 AC 3 ms
9,464 KB
testcase_21 AC 3 ms
9,540 KB
testcase_22 AC 3 ms
9,792 KB
testcase_23 AC 3 ms
9,464 KB
testcase_24 AC 3 ms
9,656 KB
testcase_25 AC 3 ms
9,496 KB
testcase_26 AC 3 ms
9,496 KB
testcase_27 AC 3 ms
9,480 KB
testcase_28 AC 3 ms
9,484 KB
testcase_29 AC 3 ms
9,648 KB
testcase_30 AC 3 ms
9,580 KB
testcase_31 AC 3 ms
9,588 KB
testcase_32 AC 3 ms
9,472 KB
testcase_33 AC 3 ms
9,492 KB
testcase_34 AC 3 ms
9,476 KB
testcase_35 AC 3 ms
9,532 KB
testcase_36 AC 3 ms
9,472 KB
testcase_37 AC 3 ms
9,476 KB
testcase_38 AC 3 ms
9,716 KB
testcase_39 AC 3 ms
9,460 KB
testcase_40 AC 3 ms
9,480 KB
testcase_41 AC 3 ms
9,656 KB
testcase_42 AC 3 ms
9,480 KB
testcase_43 AC 3 ms
9,776 KB
testcase_44 AC 3 ms
9,460 KB
testcase_45 AC 3 ms
9,540 KB
testcase_46 AC 3 ms
9,472 KB
testcase_47 AC 3 ms
9,716 KB
testcase_48 AC 3 ms
9,528 KB
testcase_49 AC 3 ms
9,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define repn(i, n) for(int i=1;i<=n;i++)
typedef double db;
typedef pair<int,int> P;
#define fi first
#define sc second
#define all(x) x.begin(), x.end()
typedef pair<int,P> P1;
#define pb push_back
#define mp make_pair
#define INF 1000000000
typedef long long ll;
const int mod = 1000000007;
#define POSL(x, v) lower_bound(all(x), v) - x.begin()
void dmp(vector<int>vi){
    rep(i, vi.size()) cout << vi[i] << " ";
    cout << endl;
}

struct make{
	int go[905][256];
	vector<vector<int>>za;
	vector<int>norm(vector<int>vi){
	    map<int, int>M;
	    int nxt = 1;
	    rep(i, vi.size()){
	        if(vi[i] > 0){
	            if(M.find(vi[i]) == M.end()) M[vi[i]] = nxt++;
	            vi[i] = M[vi[i]];
	        }
	    }
	    return vi;
	}
	bool ok(vector<int>vi){
	    int cnt[10]={};
	    stack<int>S;
	    rep(i, vi.size()){
	        if(vi[i] == 0) continue;
	        if(S.size() && S.top() == vi[i]) S.pop(); else S.push(vi[i]);
	    }
	    if(S.size()) return 0;
	    rep(i, vi.size()) cnt[vi[i]] ++;
	    repn(i, 9){
	        if(cnt[i] != 0 && cnt[i] != 2) return 0;
	    }
	    return 1;
	}
	void rec(vector<int>vi, int n, vector<int>cur, int nxt){
	    if(vi.size() == n){
	        if(ok(vi) && vi == norm(vi)) za.pb(vi);
	        return;
	    }
	    vi.pb(0); rec(vi, n, cur, nxt); vi.pop_back();
	    if(cur.size()){
	    	vi.pb(cur.back()); cur.pop_back(); rec(vi, n, cur, nxt);
	    	cur.pb(vi.back()); vi.pop_back();
	    }
	    vi.pb(nxt); cur.pb(nxt); rec(vi, n, cur, nxt+1);
	    cur.pop_back(); vi.pop_back();
	}
}t[10];
struct uf{
	int par[16];
	void init() { rep(i, 16) par[i] = i; }
	int find(int x) { if(x == par[x]) return x; else return par[x] = find(par[x]); }
	void unite(int x, int y){
		x = find(x); y = find(y);
		if(x == y) return;
		par[x] = y;
	}
}kaede;
void init(){
	for(int n=4;n<=4;n++){
		t[n].rec(vector<int>(), n, vector<int>(), 1);
		memset(t[n].go, -1, sizeof(t[n].go));
		sort(all(t[n].za));
		int cnt = t[n].za.size();
		rep(i, cnt){
			rep(j, (1<<(n-1))){
			    int deg[16] = {};
			    rep(k, n) deg[k] = !!t[n].za[i][k];
				rep(q , n-1) if(((j >> q)&1)) deg[q]++, deg[q+1]++;
				bool bad = 0;
				//次数が2より大きかったらアウト
				rep(k, n) if(deg[k] > 2) bad = 1;
				if(bad) continue;   
				vector<int>nxt = t[n].za[i];
				kaede.init();
				//今頂点がoffのところには適当に大きい値を割り振る
				int id = 6;
				rep(q, n) if(nxt[q] == 0) nxt[q] = id++;
				rep(q , n-1) if(((j >> q)&1)) kaede.unite(nxt[q], nxt[q+1]);
				int mn[16]; rep(i, 16) mn[i] = INF;
				//連結成分ごとに一番小さいIDを使えば良い
				rep(q, 16) mn[kaede.find(q)] = min(mn[kaede.find(q)], q);
				//次数が1以上の連結成分を考え、そのうち次数 = 2のものは消える
				rep(q, n){
					if(deg[q] == 0) nxt[q] = 0;
					else nxt[q] = mn[kaede.find(nxt[q])];
				}
				bool ex[16] = {}, en[16] = {};
				rep(q, n){
					if(deg[q] == 1) ex[nxt[q]] = 1;
					else if(deg[q] == 2) en[nxt[q]] = 1;
				}
				int del = 0, zan = 0;
				rep(i, 16){
					if(ex[i]) zan ++;
					else if(en[i]) del ++;
				}
				if(del == 0) {
				    rep(q, n){
    					if(deg[q]%2 == 0) nxt[q] = 0;
    					else nxt[q] = mn[kaede.find(nxt[q])];
    				}
					auto gt = t[n].norm(nxt);
					int A = POSL(t[n].za, gt);
					if(A == t[n].za.size() || t[n].za[A] != gt);
					else t[n].go[i][j] = A;
				}
				else if(del == 1 && zan == 0){
					//end of cycle
					t[n].go[i][j] = t[n].za.size();
				}
			}
		}
	}
}

ll way[10][105], ans[10][105];
int cnt[10][8];
template<class T>
void add(T &a, T b){
	a += b;
	if(a < 0) a += mod;
	if(a >= mod) a -= mod;
}
void sol(){
	int n = 3;
	int sz = t[n+1].za.size()+1;
	rep(i, sz-1){
		rep(j, (1<<n)){
			auto vt = t[n+1].za[i];
			rep(x, n) if(((j>>x)&1)) {
				vt[x]++;
				vt[x+1]++;
			}
			rep(x, n+1) cnt[i][j] += !!vt[x];
		}
	}
	way[0][0] ++;
	repn(i, (1<<n)-1){
		if(t[n+1].go[0][i] == -1) continue;
		way[t[n+1].go[0][i]][0] ++;
		ans[t[n+1].go[0][i]][0] += cnt[0][i];
	}
	rep(j, 100){
		rep(i, sz){
			rep(mask, (1<<n)){
				if(i != sz-1){
					int to = t[n+1].go[i][mask];
					if(to == -1) continue;
					add(way[to][j+1], way[i][j]);
					add(ans[to][j+1], ans[i][j]);
					add(ans[to][j+1], way[i][j]*cnt[i][mask]%mod);
				}
				else if(mask == 0){
					add(way[sz-1][j+1], way[i][j]);
					add(ans[sz-1][j+1], ans[i][j]);
				}
			}
		}
	}
	int nn; cin >> nn;
	cout << ans[sz-1][nn] << endl;
}
int main(){
	init();
	sol();
}
0