結果
| 問題 | No.579 3 x N グリッド上のサイクルのサイズ(hard) |
| ユーザー |
 fumofumofuni
|
| 提出日時 | 2022-08-28 19:19:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 9 ms / 2,000 ms |
| コード長 | 9,842 bytes |
| コンパイル時間 | 3,851 ms |
| コンパイル使用メモリ | 241,116 KB |
| 最終ジャッジ日時 | 2025-02-06 22:59:41 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 80 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=(n)-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={0,1,0,-1,1,1,-1,-1,0};
const ll dx[9]={1,0,-1,0,1,-1,1,-1,0};
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int mod = MOD;
const int max_n = 200005;
struct mint {
ll x; // typedef long long ll;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
mint operator+(const mint a) const { return mint(*this) += a;}
mint operator-(const mint a) const { return mint(*this) -= a;}
mint operator*(const mint a) const { return mint(*this) *= a;}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
bool operator==(const mint &p) const { return x == p.x; }
bool operator!=(const mint &p) const { return x != p.x; }
// for prime mod
mint inv() const { return pow(mod-2);}
mint& operator/=(const mint a) { return *this *= a.inv();}
mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
using vm=vector<mint>;
using vvm=vector<vm>;
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
}comb(max_n);
struct UnionFind {
vector<int> par;
vector<int> edge;
UnionFind(int n) : par(n, -1),edge(n, 0) {}
int root(int x) {
if (par[x] < 0) return x;
else return par[x] = root(par[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x == y) {
edge[x]++;
return false;
}
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
edge[x] += edge[y]+1;
return true;
}
int size(int x) {
return -par[root(x)];
}
};
ll score(ll bit){
if(bit==7||bit==5)return 4;
if(__builtin_popcount(bit)==2)return 3;
return 2;
}
ll sc(vl v){
ll bit=0;
rep(i,3)if(v[i])bit|=1<<i;
return score(bit);
}
mint solve(ll n){
map<pair<vl,ll>,mint> dp;
mint ans=0;
rep(_,n+1){
map<pair<vl,ll>,mint> ndp;
for(auto [x,ret]:dp){
auto [v,leng]=x;
if(v.back()!=2)ans+=ret*(leng+sc(v));
}
for(auto [x,rrr]:dp){
auto [v,leng]=x;
repl(bit,1,1<<3){
ll cir=0;
if(bit==7&&v==(vl){1,0,1})continue;//穴あきの防止
{//自己交差の防止
vl nnn;
nnn.push_back(bit>>0&1);
nnn.push_back(bit>>1&1);
nnn.push_back(min(1LL,v[0]));
nnn.push_back(min(1LL,v[1]));
if(nnn==(vl){1,0,0,1}||nnn==(vl){0,1,1,0})continue;
if(nnn!=(vl){1,1,1,1}&&nnn!=(vl){0,0,0,0})cir++;
}
{
vl nnn;
nnn.push_back(bit>>1&1);
nnn.push_back(bit>>2&1);
nnn.push_back(min(1LL,v[1]));
nnn.push_back(min(1LL,v[2]));
if(nnn==(vl){1,0,0,1}||nnn==(vl){0,1,1,0})continue;
if(nnn!=(vl){1,1,1,1}&&nnn!=(vl){0,0,0,0})cir++;
}
{
vl nnn;
nnn.push_back(bit>>0&1);
nnn.push_back(min(1LL,v[0]));
if(nnn!=(vl){0,0})cir++;
}
{
vl nnn;
nnn.push_back(bit>>2&1);
nnn.push_back(min(1LL,v[2]));
if(nnn!=(vl){0,0})cir++;
}
UnionFind uf(6);
if(v[0]&&v[1])uf.merge(0,1);
if(v[1]&&v[2])uf.merge(1,2);
if(v[0]&&(bit>>0&1))uf.merge(0,3);
if(v[1]&&(bit>>1&1))uf.merge(1,4);
if(v[2]&&(bit>>2&1))uf.merge(2,5);
if((bit>>0&1)&&(bit>>1&1))uf.merge(3,4);
if((bit>>1&1)&&(bit>>2&1))uf.merge(4,5);
if(v[0]==v[2]&&v[0])uf.merge(0,2);
vl nv={0,0,0};
rep(i,3){
rep(j,3){
if(uf.same(i,j+3))nv[i]=1;
}
}
if(v[0]&&nv[0]==0)continue;
if(v[1]&&nv[1]==0)continue;
if(v[2]&&nv[2]==0)continue;
vl con(3);map<ll,ll> mp;ll now=1;
rep(i,3){
if(bit>>i&1){
ll p=uf.root(i+3);
if(mp.count(p))con[i]=mp[p];
else{
mp[p]=now;now++;
con[i]=mp[p];
}
}
}
ndp[{con,leng+cir}]+=rrr;
}
}
ndp[{{0,0,1},2}]+=1;
ndp[{{0,1,1},3}]+=1;
ndp[{{1,1,1},4}]+=1;
ndp[{{0,1,0},2}]+=1;
ndp[{{1,0,0},2}]+=1;
ndp[{{1,1,0},3}]+=1;
ndp[{{1,0,2},4}]+=1;
swap(dp,ndp);
}
return ans;
}
vector<mint> BerlekampMassey(const vector<mint> &s) {
const int N = (int)s.size();
vector<mint> b, c;
b.reserve(N + 1);
c.reserve(N + 1);
b.push_back(mint(1));
c.push_back(mint(1));
mint y = mint(1);
for (int ed = 1; ed <= N; ed++) {
int l = int(c.size()), m = int(b.size());
mint x = 0;
for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i];
b.emplace_back(mint(0));
m++;
if (x == mint(0)) continue;
mint freq = x / y;
if (l < m) {
auto tmp = c;
c.insert(begin(c), m - l, mint(0));
for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i];
b = tmp;
y = x;
} else {
for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i];
}
}
reverse(begin(c), end(c));
return c;
}
template <typename mint>
vector<mint> kitamasa(vector<mint> Q,vector<mint> a) {
assert(!Q.empty() && Q[0] != 0);
assert((int)a.size() >= int(Q.size()) - 1);
vector<mint> P(Q.size()*2-2);
for(ll i=0;i<Q.size()-1;i++){
for(ll j=0;j<Q.size();j++){
P[i+j]+=a[i]*Q[j];
}
}
P.resize(Q.size() - 1);
return P;
}
template<class T>
struct bostan_mori {
vector<T> p, q;
bostan_mori(vector<T> &_p, vector<T> &_q) : p(_p), q(_q) {}
void rever(vector<T> &f) const {
int d = f.size();
rep(i, d) if (i&1) f[i] = -f[i];
}
void even(vector<T> &f) const {
int d = (f.size() + 1) >> 1;
rep(i, d) f[i] = f[i<<1];
f.resize(d);
}
void odd(vector<T> &f) const {
int d = f.size() >> 1;
rep(i, d) f[i] = f[i<<1|1];
f.resize(d);
}
vector<T> convolution(vector<T> a,vector<T> b) const{
int n=a.size(),m=b.size();
vector<T> c(n+m-1);
rep(i,n)rep(j,m)c[i+j]+=a[i]*b[j];
return c;
}
T operator[] (ll n) const {
vector<T> _p(p), _q(q), _q_rev(q);
rever(_q_rev);
for (; n; n >>= 1) {
_p = convolution(move(_p), _q_rev);
if (n&1) odd(_p);
else even(_p);
_q = convolution(move(_q), move(_q_rev));
even(_q);
_q_rev = _q; rever(_q_rev);
}
return _p[0] / _q[0];
}
};
//https://nyaannyaan.github.io/library/fps/kitamasa.hpp
//https://atcoder.jp/contests/tdpc/submissions/34362182
//線形漸化式のprefixからn項目を復元できる。
bostan_mori<mint> interpolation(vm a){
auto q=BerlekampMassey(a);
auto p=kitamasa(q,a);
return bostan_mori<mint>(p,q);
}
vm ps={
0,
32,
316,
2292,
14422,
84744,
479004,
2638328,
14258574,
75940592,
399782668,
84795558,
786749020,
442043859,
352536615,
76576421,
744912747,
420315017,
25759333,
562730793,
424899366,
153177921,
250747498,
306910436,
324829483,
572545341,
104022619,
226237183,
421453002,
754280938,
291624319,
60437277,
297658752,
677142927,
63550828,
801541292,
683008492,
650348,
519624175,
715484025,
724658778,
152363657,
280344328,
892278238,
206785631,
227202296,
788486407,
392284243,
927772200,
781378846,
881515964,
905982211,
674841192,
139044658,
711210295,
384364637,
137653614,
441363040,
812818651,
929556368,
494420762,
802527485,
700803632,
461521718,
152786116,
688977792,
48724029,
642700933,
15567410,
246397043,
859581827,
685250826,//71
};
int main(){
ll n;cin >> n;
auto ip=interpolation(ps);
cout << ip[n] << endl;
}