yukicoder : No.303 割れません

多倍長整数付言語だとギリギリ。
http://yukicoder.me/problems/831

問題

長さk(kは奇数)の素材がk円で手に入る。
また1円で手持ちの素材を2つに分割することができる。

素材を連結して長さLにしたい。
ただし、Lの中心(端からL/2の位置)が素材の継ぎ目になるようなことは避けたい。

必要な最小金額と、その最小金額を達成する素材の連結方法の組み合わせ総数を求めよ。

解法

素材の分割が発生しなければ、最小金額は長さに等しいL円になる。
Lが奇数なら長さLの素材を調達すればよいので最小金額はL円である。
Lが偶数なら、長さ(L/2+1)と(L/2-1)の素材を調達すればよいのでやはり最小金額はL円である。

例外としてL==2がある。
この場合、今回素材の分割位置は整数に限らないので、長さ1の素材を2つ入手し、片方をσ,1-σに分けて3つの素材をσ,1,1-σの順に連結すると題意を満たす。
σは0と1の間の実数なら何でも良いので、組み合わせ総数は無限である。

L==2の例外ケースを除くと、この問題は以下のように言い換えられる。

• Lを奇数の和として表現する場合の(並び順も含めた)組み合わせ総数を求める。
• ただし、Lが偶数のとき、途中までの和がL/2となるケースは除く。

前者の値をF(L)とする。
Lが奇数なら解はF(L)、偶数ならF(L)-F(L/2)^2を返せばよい。

残るはF(L)の計算である。
F(L)をDPで求めると、これはフィボナッチ数列であることがわかる。
実際、F(L)は(L-(奇数))の長さの連結素材に最後奇数長の素材を連結して作ると考えると以下のように計算できる。

• 
• 

F(L)がフィボナッチ数列ならF(L-p)=F(L-p+1)-F(L-p-1)と置き換えられるので、上記後者の式が成り立つことがわかる。

あとは頑張ってフィボナッチ数列の第L項を求めよう。
漸化式を行列累乗テクで計算していくと、辛うじて間に合う。
自分の方法はPyPyでも9秒弱とギリギリだった。

L=input()

def fib(L):
	if L<3:
		return 1
	v1=v2=a=b=c=1
	d=0
	L-=2
	while L:
		if L%2:
			v2,v1=a*v2+b*v1,c*v2+d*v1
		L /= 2
		bc=b*c
		a,b,c,d=a*a+bc,b*(a+d),c*(a+d),bc+d*d
	return v2


if L==2:
	print 3
	print "INF"
else:
	ret = fib(L)
	if L%2==0:
		ret -= fib(L/2)**2
	
	print L
	print ret

まとめ

他のコンテストなら、たぶん多倍長じゃなくて10^9+7の剰余を取らせるよな…。