結果
| 問題 |
No.541 3 x N グリッド上のサイクルの個数
|
| コンテスト | |
| ユーザー |
 はむこ
|
| 提出日時 | 2017-06-02 23:55:38 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 6,677 bytes |
| コンパイル時間 | 1,809 ms |
| コンパイル使用メモリ | 169,540 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-22 12:41:16 |
| 合計ジャッジ時間 | 3,293 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 62 |
ソースコード
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) {}
ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
signed a = x, b = MOD, u = 1, v = 0;
while(b) {
signed t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
if(u < 0) u += Mod;
ModInt res; res.x = (unsigned)u;
return res;
}
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;
typedef vector<mint> vmint;
ostream &operator<<(ostream &o, const mint v) { o << v.x; return o; }
// GF(mo)列sから、それを生成する最小線形漸化式Cを復元する
//
// 入力: 漸化式が生成したGF(mo)列s
// 出力: d項間漸化式の係数C (size = d+1)
// 漸化式
// C_0 s_{n} + C_1 s_{n-1} + ... + C_{L} s{n-L} = 0
// がsを生成した時、Cを求める。
//
// O(n^2)
//
// 例:
// s = [1, 2, 4, 8] -> C = [1, 1000000005(-2)] (s[1] - 2 * s[0] = 0)
// s = [1, 1, 1, 1] -> C = [1, 1000000006(-1)] (s[1] - s[0] = 0)
int berlekampMassey(const vector<mint> &s, vector<mint> &C) {
int N = (int)s.size();
C.assign(N + 1, mint());
vector<mint> B(N + 1, mint());
C[0] = B[0] = 1;
int degB = 0;
vector<mint> T;
int L = 0, m = 1;
mint b = 1;
for(int n = 0; n < N; ++ n) {
mint d = s[n];
for(int i = 1; i <= L; ++ i)
d += C[i] * s[n - i];
if(d == mint()) {
++ m;
} else {
if(2 * L <= n)
T.assign(C.begin(), C.begin() + (L + 1));
mint coeff = -d * b.inverse();
for(int i = -1; i <= degB; ++ i)
C[m + i] += coeff * B[i];
if(2 * L <= n) {
L = n + 1 - L;
B.swap(T);
degB = (int)B.size() - 1;
b = d;
m = 1;
} else {
++ m;
}
}
}
C.resize(L + 1);
return L;
}
// GF(mo)列aから、それを生成する最小線形漸化式\phiを復元する
// berlekampMasseyとの違いは、係数の順序が違うのと安全用のassertチェックがあること。
//
// 入力: 漸化式が生成したGF(mo)列a
// 出力: d項間漸化式の係数\phi (size = d+1)
// 漸化式
// \phi_0 a_{i} + \phi_1 a_{1} + ... + \phi_L a_L = 0
// がaを生成した時、\phiを求める。
//
// O(n^2)
//
// 例:
// s = [1, 2, 4, 8] -> C = [1000000005(-2), 1] (s[1] - 2 * s[0] = 0)
// s = [1, 1, 1, 1] -> C = [1000000006(-1), 1] (s[1] - s[0] = 0)
void computeMinimumPolynomialForLinearlyRecurrentSequence(const vector<mint> &a, vector<mint> &phi) {
assert(a.size() % 2 == 0);
int L = berlekampMassey(a, phi);
reverse(phi.begin(), phi.begin() + (L + 1));
}
// 漸化式
// \phi_0 a_{i} + \phi_1 a_{1} + ... + \phi_L a_L = 0
// と、initValues = a[0:phi.size()-1]が与えられる。
// この時、a[k]をinitValues(=a[0:phi.size()-1])の線形結合の係数を返す。
// a[k] = coeff[0] * initValues[0] + coeff[1] * initValues[1] + ... + coeff[d-1] * initValues[d-1]
//
// O(n^2 log k)
void linearlyRecurrentSequenceCoeffs(long long k, const vector<mint> &phi_in, vector<mint> &coeffs) {
int d = (int)phi_in.size() - 1;
assert(d >= 0);
assert(phi_in[d].get() == 1);
coeffs = vector<mint>(d);
vector<mint> square;
coeffs[0] = 1;
int l = 0;
while ((k >> l) > 1) ++l;
for (; l >= 0; --l) {
square.assign(d * 2 - 1, mint());
rep(i, d) rep(j, d) square[i + j] += coeffs[i] * coeffs[j];
for (int i = d * 2 - 2; i >= d; -- i) {
mint c = square[i];
if (c.x == 0) continue;
rep(j, d) square[i - d + j] -= c * phi_in[j];
}
rep(i, d)
coeffs[i] = square[i];
if (k >> l & 1) {
mint lc = coeffs[d - 1];
for(int i = d - 1; i >= 1; -- i)
coeffs[i] = coeffs[i - 1] - lc * phi_in[i];
coeffs[0] = mint() - lc * phi_in[0];
}
}
}
// 漸化式
// \phi_0 a_{i} + \phi_1 a_{1} + ... + \phi_L a_L = 0
// と、initValues = a[0:phi.size()-1]が与えられる。
// この時、
// a_{k}を求める
//
// O(n^2 log k)
//
// また、副産物として、a[k]をinitVectorの線形結合として表す係数coeffが得られる
// a[k] = coeff[0] * initValues[0] + coeff[1] * initValues[1] + ... + coeff[d-1] * initValues[d-1]
//
mint linearlyRecurrentSequenceValue(long long k, const vector<mint> &initValues, const vector<mint> &phi) {
int d = phi.size() - 1;
if(d == 0) return mint();
assert(d <= (int)initValues.size());
assert(k >= 0);
if(k < (int)initValues.size())
return initValues[(int)k];
vector<mint> coeffs;
linearlyRecurrentSequenceCoeffs(k, phi, coeffs);
mint res; rep(i, d) res += coeffs[i] * initValues[i];
return res;
}
// 線形漸化的数列aのk番目は？
// O(n^2 log k)
mint reconstruct(long long k, vector<mint> a) {
if (a.size() % 2) a.pop_back();
vector<mint> a_first_half;
rep(i, a.size() / 2)
a_first_half.pb(a[i]);
vector<mint> phi;
computeMinimumPolynomialForLinearlyRecurrentSequence(a, phi);
return linearlyRecurrentSequenceValue(k, a_first_half, phi);
}
vector<mint> a = {0, 6, 40, 213, 1049, 5034, 23984, 114069, 542295, 2577870, 12253948, 58249011, 276885683, 316170983};
int main(void) {
ll n; cin >> n;
cout << reconstruct(n, a) << endl; // めんどいのでBerlekamp-Masseyで復元
return 0;
}