結果
問題 | No.579 3 x N グリッド上のサイクルのサイズ(hard) |
ユーザー |
![]() |
提出日時 | 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; | ^~
ソースコード
#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 1000000000typedef 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 cyclet[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();}