#467960 (C++17) No.578 3 x N グリッド上のサイクルのサイズ(easy)

提出ソース

結果

問題	No.578 3 x N グリッド上のサイクルのサイズ(easy)
ユーザー	HIR180
提出日時	2020-04-22 01:20:11
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4 ms / 2,000 ms
コード長	4,545 bytes
コンパイル時間	3,098 ms
コンパイル使用メモリ	231,584 KB
実行使用メモリ	11,844 KB
最終ジャッジ日時	2024-10-09 16:54:46
合計ジャッジ時間	4,837 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 9,672 KB
testcase_01	AC	4 ms 9,544 KB
testcase_02	AC	3 ms 9,800 KB
testcase_03	AC	3 ms 9,668 KB
testcase_04	AC	3 ms 9,804 KB
testcase_05	AC	3 ms 9,800 KB
testcase_06	AC	4 ms 9,668 KB
testcase_07	AC	4 ms 9,668 KB
testcase_08	AC	4 ms 9,672 KB
testcase_09	AC	4 ms 11,716 KB
testcase_10	AC	3 ms 9,804 KB
testcase_11	AC	3 ms 9,672 KB
testcase_12	AC	4 ms 11,716 KB
testcase_13	AC	4 ms 9,672 KB
testcase_14	AC	3 ms 9,672 KB
testcase_15	AC	3 ms 9,668 KB
testcase_16	AC	3 ms 9,796 KB
testcase_17	AC	4 ms 11,720 KB
testcase_18	AC	3 ms 9,668 KB
testcase_19	AC	4 ms 9,800 KB
testcase_20	AC	4 ms 9,672 KB
testcase_21	AC	3 ms 9,800 KB
testcase_22	AC	3 ms 9,672 KB
testcase_23	AC	3 ms 9,672 KB
testcase_24	AC	3 ms 9,804 KB
testcase_25	AC	3 ms 9,668 KB
testcase_26	AC	3 ms 9,672 KB
testcase_27	AC	3 ms 9,800 KB
testcase_28	AC	3 ms 11,844 KB
testcase_29	AC	4 ms 9,800 KB
testcase_30	AC	4 ms 9,672 KB
testcase_31	AC	3 ms 11,716 KB
testcase_32	AC	4 ms 9,672 KB
testcase_33	AC	3 ms 9,548 KB
testcase_34	AC	3 ms 9,808 KB
testcase_35	AC	4 ms 9,668 KB
testcase_36	AC	4 ms 9,676 KB
testcase_37	AC	3 ms 9,672 KB
testcase_38	AC	4 ms 11,716 KB
testcase_39	AC	4 ms 9,796 KB
testcase_40	AC	3 ms 9,672 KB
testcase_41	AC	3 ms 9,668 KB
testcase_42	AC	3 ms 11,840 KB
testcase_43	AC	3 ms 9,544 KB
testcase_44	AC	3 ms 9,672 KB
testcase_45	AC	3 ms 9,672 KB
testcase_46	AC	3 ms 9,672 KB
testcase_47	AC	3 ms 9,800 KB
testcase_48	AC	3 ms 9,676 KB
testcase_49	AC	3 ms 9,800 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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();
}

yukicoder

結果

テストケース

ソースコード