結果

問題 No.579 3 x N グリッド上のサイクルのサイズ(hard)
ユーザー HIR180HIR180
提出日時 2020-04-22 01:41:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 6,402 bytes
コンパイル時間 3,885 ms
コンパイル使用メモリ 230,284 KB
最終ジャッジ日時 2025-01-09 22:13:58
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::vector<long long int> BerlekampMassey(std::vector<long long int>)’:
main.cpp:163:30: warning: ‘lf’ may be used uninitialized [-Wmaybe-uninitialized]
  163 |                 vector<ll>c(i-lf-1);
      |                             ~^~~
main.cpp:151:13: note: ‘lf’ was declared here
  151 |         int lf,ld;
      |             ^~
main.cpp:162:40: warning: ‘ld’ may be used uninitialized [-Wmaybe-uninitialized]
  162 |                 ll k = -(x[i]-t)*modpow(ld,mod-2)%mod;
      |                                  ~~~~~~^~~~~~~~~~
main.cpp:151:16: note: ‘ld’ was declared here
  151 |         int lf,ld;
      |                ^~

ソースコード

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()
template<class T>
void dmp(vector<T>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 modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll way[10][55], ans[10][55];
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;
}
vector<ll>BerlekampMassey(vector<ll>x){
	vector<ll>ls,cur;
	int lf,ld;
	rep(i,x.size()){
		ll t = 0;
		for(int j=0;j<cur.size();j++){
			t = (t+x[i-j-1]*cur[j])%mod;
		}
		if( ((t-x[i])%mod+mod)%mod == 0 ) continue;
		if(!cur.size()){
			cur.resize(i+1); lf = i; ld = (t-x[i])%mod;
			continue;
		}
		ll k = -(x[i]-t)*modpow(ld,mod-2)%mod;
		vector<ll>c(i-lf-1);
		c.pb(k);
		rep(j,ls.size()) c.pb(-ls[j]*k%mod);
		if(c.size() < cur.size()) c.resize(cur.size());
		rep(j,cur.size()){
			c[j]=(c[j]+cur[j])%mod;
		}
		if(i-lf+(int)(ls.size()) >= (int)(cur.size())){
			ls = cur, lf = i, ld = (t-x[i])%mod;
		}
		cur = c;
	}
	rep(i,cur.size()) cur[i] = (cur[i]%mod+mod)%mod;
	return cur;
}
vector<ll>shrink(vector<ll>&a){ while(a.size()&&a.back()==0) a.pop_back(); return a;}
vector<ll>mul(vector<ll>a, vector<ll>b){
	vector<ll>ret (a.size()+b.size()-1, 0);
	rep(i, a.size()) rep(j, b.size()) add(ret[i+j], a[i]*b[j]%mod);
	return ret;
}
vector<ll>gmod(vector<ll>a, vector<ll>b){
	while(a.size() >= b.size()){
		ll c = a.back() * modpow(b.back(), mod-2) % mod;
		rep(i, b.size()){
			add(a[i+a.size()-b.size()], mod-(c*b[i])%mod);
		}
		shrink(a);
	}
	return a;
}
vector<ll>get_mod(vector<ll>a, ll n, vector<ll>b){
	vector<ll>ret = {1};
	while(n){
		if(n & 1) {
			ret = mul(ret, a);
			ret = gmod(ret, b);
		}
		a = mul(a, a);
		a = gmod(a, b);
		n >>= 1;
	}
	return ret;
}
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, 50){
		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]);
				}
			}
		}
	}
	ll id ; cin >> id;
	if(id <= 50){
		cout << ans[sz-1][id] << endl;
		return;
	}
	vector<ll>res;
	for(int x=10;x<=50;x++) res.pb(ans[sz-1][x]);
	auto linear = BerlekampMassey(res);
	for(auto &at:linear) at = (mod-at)%mod;
	reverse(all(linear)); linear.pb(1);
	auto vec = get_mod( {0, 1}, id-10, linear );
	ll ret = 0;
	rep(i, vec.size()) ret += 1LL*ans[sz-1][10+i]*vec[i]%mod;
	cout << (ret%mod+mod)%mod << endl;
}
int main(){
	init();
	sol();
}
0