E:FPS解を考える
最終的に左右に動かす数をLとRとすると
m個をL+R種類(最低一回は使用)で塗る場合の数は
[x^m](e^x-1)^(L+R)*m!であり
(e^xとm!は展開すると7!/(3!*2!*2!)みたいな形になるので求めたいものがもとまる)
最後のm-(L+R)以外は左右が自由なのと
L種とR種の順番を考慮する必要があるので
[x^m](e^x-1)^(L+R) * 2^(m-(L+R)) * m! / (L!*R!)
を求めたい
そのために[x^m](e^x-1)^kを先に考える
(e^x-1)^k = Σc(k,i)*(-1)^(k-i)*(e^x)^i
=Σc(k,i)*(-1)^(k-i)*(e^xi)
なので
[x^m](e^x-1)^k=Σc(k,i)*(-1)^(k-i)*i^m/m!
なので前計算パートがO(k^2)で収まること
本計算パートもO(k^2)で収まるので十分高速
