すごい面白かった!!!
問題概要
整数 が与えらえたときに、漸化式
を満たす数列 が与えられる。これに対して以下の 個のクエリに答えよ:
- 1 つのクエリは 2 以上の整数 が指定され、 を満たすような正の整数 に対して、 の総和を求め、1000000007 で割ったあまりを求めよ。
制約
数列の母関数
いかにも畳み込みっぽい式をしているので、母関数 (形式的べき級数) で考えてみたくなる。さて、線形漸化式の形で書かれた数列の母関数は実は簡単に求められる。
まず数列 の母関数とは、
で定義される関数のこと。求めたい数列に対して、母関数がわかれば、その係数を見ることで数列の各項がわかる、みたいなことがよくある。
さて、たとえば例として三項間漸化式
で定義される数列の母関数を形式的に求めてみよう。
として、これらを足すと、なんとほとんどの項が消えてしまうのだ。なぜなら漸化式の定義から、
- ...
が成立するからだ。足すと
⇔
と求められる。
今回の数列
今回の数列 (0-indexed にして、クエリの も 引いておく) の母関数を とすると、
と求められる。ここで、
によって定義される数列 の母関数 を求めることにする。数列 の定義をよくよく考えると、
の各項の係数になっていることがわかる。よって単純に
なのだ!!!実際に計算してみると、
となる。ちなみに分子の は恐れる必要はない。母関数を 倍したり で割ったりするのは、対応する数列の添字をずらす操作に他ならない。 は、むしろ母関数としては
と表されるものがわかりやすくて、これを漸化式に直すと
となる!!!実際はこれに を割るので、項が 1 個だけずれることになる。よって数列 は、
で求められるので、あらかじめ制約の 程度まで求めておけば OK!!!
#include <bits/stdc++.h> using namespace std; template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; const int MAX = 2100000; const int MOD = 1000000007; using mint = Fp<MOD>; int main() { long long lp; cin >> lp; vector<mint> b(MAX, 0); mint p = lp; b[2] = 1, b[3] = p * 2; for (int n = 4; n < MAX; ++n) { b[n] = b[n-1]*p*2 - b[n-2]*(p*p-2) - b[n-3]*p*2 - b[n-4]; } int Q; cin >> Q; for (int _ = 0; _ < Q; ++_) { int q; cin >> q; q -= 2; cout << b[q] << endl; } }