二段階右折 P-recursive
概要
2 次元数列の特定の項$ a(N,M) を求めたいとします。
P-recursive で解説した方法を素直に 2 次元に拡張すると、$ N 以下の$ i と$ M 以下の$ j の組全てに対する$ a(i,j) を昇順に求めていく漸化式を復元する方法が得られます。 しかしこれでは計算量が $ \Theta(N M) になり、$ N, M が大きいときは使えません。
そこで次のような方法で計算量を $ O(N+M) に落とします。
小さめの $ j=0,1,\dots それぞれについて $ a(0,j), a(1,j), \dots が求まっていれば、P-recursive で解説した方法で $ a(N,j) がそれぞれ得られます。 再度$ a(N,0), a(N,1), \dots に対して似た手法を適用することで$ a(N,M) が得られます。
ただし 2 段階目では、係数の推定には $ a(i,j) を全て使えますが、漸化式を用いた 2 次元数列の延長には $ a(N,j) しか使えないことに注意が必要です。
使用例
DFS で必要な項を集める。
DFS で必要な項を集める。
2 次元 DP で必要な項を集める。
多項式オーダーの DP で必要な項を集める。
2 つの問題に分解し、Mathematica の Expand や Coefficient で必要な項を集める。
0 除算で延長に失敗するが、対称性を利用して対処可能。
0 除算で延長に失敗するが、そのラインだけ別途 1次元 P-recursive を適用すればいい。
得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められるので、CForm で整形して貼れば良い。
得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められる。
Narayana 数っぽいものを求められれば良いことに気付ければ本手法の 3 次元版が使える。さらに得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められる。
項数が足りないので LLL を利用する。
$ N,M が小さいので 2 段階でない素朴な方法で良い。埋めるのは下三角部分だけだが同様の手法が使える。
3 次元の例。多項式オーダーにまで落としてしまえば必要な項数は十分手に入る。
得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められるので、CForm で整形して貼ればいい。
$ N,M が小さいので 2 段階でない素朴な方法で良い。
文字列を出力する問題だが、適当に数値にエンコードしてこの手法を適用すればいい。得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められる。
得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められる。
確率を求める問題と思えば本手法が使える。
確率を求める問題と思えば本手法が使える。
各 $ A_i の寄与係数を求める問題と思えば本手法が使える。
得られた初項と漸化式に対し Mathematica で RSolve を使えば一般項まで求められる。
BFS で必要な項を集める。
bit 全探索で必要な項を集める。
適切にテーブルを整形してから本手法を使えばいい。
bit 全探索で必要な項を集める。
順列全探索で必要な項を集める。少し足りないが、LLL を併用することで漸化式を復元できる。
元ポスト
など