P-recursive
易しい解説
具体例で説明します。
$ f[0..4] = [1, 1, 2, 6, 24]
が従う漸化式を見つけたいとします。突然ですが、$ f が
$ (a n + b) f[n] + (c (n-1) + d) f[n-1] = 0 \; \cdots (*)
の形の漸化式を持っていると大胆予想します。
予想が正しければ $ n=1,2,3,4 を代入して得た連立方程式
$ (1a + b) 1 + (0c + d) 1 = 0
$ (2a + b) 2 + (1c + d) 1 = 0
$ (3a + b) 6 + (2c + d) 2 = 0
$ (4a + b) 24 + (3c + d) 6 = 0
に全ては 0 でない解があるはずです。
掃き出し法などで実際に連立方程式を解いてみると
$ (a, b, c, d) = (0, 1, -1, -1)
という解が見つかるので、これを式$ (*) に代入することで漸化式
$ (0 n + 1) f[n] + (-(n-1) - 1)f[n-1] = 0
を得ることができました。整理すると
$ f[n] = n f[n-1]
となります。
$ f によっては失敗しますが、式$ (*) の次数を上げたり項数を増やしたりして
$ (c_{00} n^2 + c_{01} n + c_{02}) f[n]
$ + (c_{10} (n-1)^2 + c_{11} (n-1) + c_{12}) f[n-1]
$ + (c_{20} (n-2)^2 + c_{21} (n-2) + c_{22}) f[n-2] = 0
などとしていけば成功するかもしれません。
例題
解答
入力が$ Nのみの数え上げなので本手法が使えそうです。
括弧列の正しさ判定、括弧列を木に直す、木の深さを計算する、全てライブラリ化済なので、活用して bit 全探索の愚直解を書きましょう：
code:naive_sub.cpp
mint naive_sub(int n) {
if (n == 0) return 0;
mint res = 0;
repbc(set, 2 * n, n) {
string s;
if (!valid_parenthesis_sequenceQ(s)) continue;
auto g = parenthesis_tree(s);
auto dep = depth_of_tree(g, 0);
mint sc = 0;
rep(i, n + 1) if (sz(gi) == 0) sc += depi - 1; res += sc;
}
return res;
}
これをテンプレに貼り付け、embed_coefs を実行すると、次のような出力が得られました：
code:output.cpp
constexpr int TRM = 3;
constexpr int DEG = 3;
{0,-124780544,-62390272},
{-124780544,-374341632,499122176},
{3,499122173,1} };
これを solve 内の指定された場所に貼り付けそのまま提出します。
問題なく AC することができました。
提出
他の使用例
$ O(N^2) まで高速化すれば必要な項は十分集まります。
$ Mが小さいときは P-recursive で対処可能です。$ Mが大きいときは$ M個置きに間引ける別の解法を採用します。
Mathematica 上でループのある漸化式を立て、それを解きループを無くし、必要な項を集め、係数を推定します。
1 次元ランダムウォークに読み替えられれば P-recursive で対処可能です。
$ O(N^2) まで高速化すれば必要な項は十分集まります。
$ \Sigmaを含む漸化式を立て、それを用いて必要な項を集めます。
P-recursive ではなく D-algebraic ですが同様の手法で母関数の満たす微分方程式が得られます。
後はオンライン畳込みで項を順に計算していけばいいです。
元ポスト
など