結果

問題 No.579 3 x N グリッド上のサイクルのサイズ(hard)
ユーザー HIR180
提出日時 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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0