結果
| 問題 | No.541 3 x N グリッド上のサイクルの個数 |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-02-16 10:29:19 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 227 ms / 2,000 ms |
| コード長 | 4,943 bytes |
| コンパイル時間 | 2,075 ms |
| コンパイル使用メモリ | 144,188 KB |
| 実行使用メモリ | 5,752 KB |
| 最終ジャッジ日時 | 2024-10-06 14:22:14 |
| 合計ジャッジ時間 | 15,620 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 62 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;const ll MOD=1e9+7;vector<vector<ll>> matrixmul(int l, int m, int n, vector<vector<ll>> a, vector<vector<ll>> b){vector<vector<ll>> c(l, vector<ll>(n));for(int i=0; i<l; i++){for(int j=0; j<n; j++){for(int k=0; k<m; k++){(c[i][j]+=a[i][k]*b[k][j])%=MOD;}}}return c;}vector<vector<ll>> matrixpow(int n, vector<vector<ll>> a, ll k){vector<vector<ll>> ap=a, ans(n, vector<ll>(n));for(int i=0; i<n; i++) ans[i][i]=1;while(k){if(k&1) ans=matrixmul(n, n, n, ap, ans);ap=matrixmul(n, n, n, ap, ap);k>>=1;}return ans;}struct unionfind{vector<int> par, sz;unionfind() {}unionfind(int n):par(n), sz(n, 1){for(int i=0; i<n; i++) par[i]=i;}int find(int x){if(par[x]==x) return x;return par[x]=find(par[x]);}void unite(int x, int y){x=find(x); y=find(y);if(x==y) return;if(sz[x]>sz[y]) swap(x, y);par[x]=y;sz[y]+=sz[x];}bool same(int x, int y){return find(x)==find(y);}int size(int x){return sz[find(x)];}};int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};const int n1=6;bool used[4][n1];vector<vector<P>> w;void dfs(vector<P> v){int x=v.back().first, y=v.back().second;for(int k=0; k<4; k++){int x1=x+dx[k], y1=y+dy[k];if(x1<0 || x1>=4 || y1<0 || y1>=n1) continue;if(v[0]==P(x1, y1) && v.size()>=3 && *min_element(v.begin(), v.end())==v[0]){w.push_back(v);}if(used[x1][y1]) continue;v.push_back({x1, y1});used[x1][y1]=1;dfs(v);used[x1][y1]=0;v.pop_back();}}vector<int> state;vector<vector<ll>> mat;vector<int> v0, v1;void calc(){for(int i=0; i<4; i++){for(int j=0; j<n1; j++){used[i][j]=1;vector<P> v(1, P(i, j));dfs(v);used[i][j]=0;}}int c[10101][n1];for(int l=0; l<w.size(); l++){auto v=w[l];int a[4][n1]={}, b[4][n1]={}, s[4][n1]={};for(int i=0; i<v.size(); i++){a[v[i].first][v[i].second]=i+1;}unionfind uf(4*n1);for(int i=0; i<n1; i++){for(int j=0; j<4; j++){for(int k=0; k<4; k++){int x=j+dx[k], y=i+dy[k];if(x<0 || x>=4 || y<0 || y>=n1) continue;if(a[j][i] && a[x][y] && (abs(a[x][y]-a[j][i])==1 || abs(a[x][y]-a[j][i])==v.size()-1)){b[j][i]^=(1<<k);}}}for(int j=0; j<3; j++){if(b[j][i]&1){uf.unite(i*4+j, i*4+j+1);}}for(int j=0; j<4; j++){if(b[j][i]&8){uf.unite(i*4+j, (i-1)*4+j);}}map<int, int> mp;int k=0;for(int j=0; j<4; j++){if(!a[j][i]) continue;int r=uf.find(i*4+j);if(mp.find(r)==mp.end()){s[j][i]=k;mp[r]=k;k++;}else{s[j][i]=mp[r];}}c[l][i]=0;for(int j=0; j<4; j++){s[j][i]=s[j][i]*16+b[j][i];c[l][i]^=(s[j][i]<<(6*j));}state.push_back(c[l][i]);}}sort(state.begin(), state.end());state.erase(unique(state.begin(), state.end()), state.end());int m=state.size()+1;mat.resize(m);for(int i=0; i<m; i++) mat[i].resize(m);v0.resize(m); v1.resize(m);for(int i=0; i<w.size(); i++){for(int j=0; j<n1; j++){c[i][j]=lower_bound(state.begin(), state.end(), c[i][j])-state.begin();if(j>0 && c[i][j]==0 && c[i][j-1]>0) c[i][j]=m-1;}v0[c[i][0]]|=1, v1[c[i][n1-1]]|=1;for(int j=0; j<n1-1; j++){mat[c[i][j]][c[i][j+1]]|=1;}}}int main(){ll n;cin>>n;calc();int m=state.size()+1;auto matp=matrixpow(m, mat, n);ll ans=0;for(int i=0; i<m; i++){if(!v0[i]) continue;for(int j=0; j<m; j++){if(!v1[j]) continue;(ans+=matp[i][j])%=MOD;}}cout<<ans<<endl;return 0;}