本履歴

購入した古本の履歴と時々プログラミング

A^P mod M

Ladder graph二題

半年ほど前にDiscrete And Combinatorial Mathematics: An Applied Introduction Ralph P. Crimaldi をナナメ読みしてた時期があって、
その中の練習問題にwikipedia:en:Ladder_graphL_nに関する問題があった。当時考えたことを思い出してまとめる・・・?!

Chapter 11 An Introduction to Graph Theory, Miscellaneous Exercises 13より
1.数列x_nをL_nの中からn本の辺を選んでどの2辺も頂点を共有しない選び方の総数とする。この時、x_nの漸化式を求めよ。

Chapter 12 Tree, Miscellaneous Exercises 20より
2.a_nをL_nのスパニングツリーの数とする。b_nをL_nのスパニングツリーの中で一番下の横の辺(はしごの足掛ける所で一番下)を含むものの数とする。
このとき、i)a_n=a_{n-1}+b_n を示せ、ii)b_nをa_{n-1}とb_{n-1}で表わせ、iii)a_nの漸化式を求めよ。

という問題。
解くだけではつまらないので、nが与えられた時、数列の実際の数を出力するプログラムを練習で書こうと思った。プログラムコンテストでよくありがちな出題で
1.はx_nの下3桁を出力する、2.はa_nを10**9+7で割った数(Codechefなどでよくある素数


さて、1.はx_n=x_{n-1}+x_{n-2}、いわゆるフィボナッチ数列。2.は(a_n,b_n)^T=A^n(a_0,b_0)^Tが答。Aはi),ii)から求まる2次行列。Tは転置オペレータ

鳩の巣原理

早速コーディングにかかったのだけど、1.はmod 1000なので、wikipedia:jp:鳩の巣原理を使いたくなった。
つまり、直前の2項で次の項が決まるのだから、x_0からx_1000000の間に連続する2項で同じ数のものが出てくるはず。
従ってそれ以降x_nは(正確にはx_n mod 1000だけど、これ以降mod略)はループする。ループするまでの項数kと周期lが求められれば、あとは計算は簡単なはず。
早速ぐだぐだ書き始めたのだけど、どうもうまくプログラムが書けなくて(境界条件でおかしくなる)、1.は後回しで、2.を考え始めた。

A^P mod M

2.は、(a_n,b_n)^T=A(a_{n-1},b_{n-1})^T=...=A^n(a_0,b_0)^T
と式変形できるので、結局A^nを求めればOK。Bを単位行列として、nを2進数表示して下の桁から順に、
B=B*A mod M if ビットが立っていたら
A=A*A mod M
を実行すれば、nのbit数のループで計算できてしまう。

実は1.も同じように考えることができて、
x_{n+1}=x_n+x_{n-1}=2*x_{n-1}+x_{n-2}
x_n=x_{n-1}+x_{n-2}
と式変形すれば、数列は一つだけど、2.のように2次の行列のn乗に帰着することができる。
結局この方法で1.も解いて当初の目的は果たしたのだけど、自分が何故鳩の巣原理を使おうと思ったのか、それが気になった。
色々考えてみたところ、昔数学を嗜んでいた関係で、どうも計算量とか関係なしにエレガントな解法を求めてしまう、のかなーと感じる。
じゃあ、鳩の巣原理がエレガントなのかよと言われると、よくわからないのだが。
例えば、A,Pを正整数としてA^P mod 1000を求めるときに、鳩の巣原理を使うのか、と考えると答えはNoなんだよなー。

結論

んで、これからはA^P mod Mで漸化式は求めよう、というお話でした。
問題出題者の方へは、mod 1000の問題を作るとハマる人がいるので、10**9+7で割るだけでは知恵がないよ、と言っておこう。んだば