yukicoder : No.148 試験監督（3）

受験生を区別しないと勘違いしていた時点でどうしようもなかった。
埋め込みまでは気づいたんだけどなぁ。
http://yukicoder.me/problems/371

問題

T個のテストケースがあり、各テストケースではC,Pが与えられる。

各テストケースでは、C個の席が一列に並ぶ机において、隣同士に受験生が座らないようにP人の受験生が着席する組み合わせを求め、の剰余を求めよ。

解法

以下の積になる。

• P人の並び方が通り。
• C席にP人を並べる方法は、P人分の席および間に1席ずつ(P-1)席を足した(2*P-1)席を除いた余りの席を両端またはP人の間の(P+1)箇所に配置する方法なので重複組み合わせで通り。

なら明らかにこの積はの倍数なので解は0。
それ以外の場合、となり(C-2*P+2)から(C-P+1)の積にになる。

(C-2*P+2)から(C-P+1)の間にの倍数があれば解は0。
無ければ、を求める。
この分子分母はそれぞれ未満の整数の階乗になるが、正攻法では階乗計算が制限時間に間に合わない。
そこで区切りで階乗値を埋め込みを使うことで回避できる。

import sys
import math


T=input()
mo=1000000007

facts=[
[0,1],
[1000000,641102369],
[2000000,578095319],
[3000000,5832229],
(略)
[997000000,822439091],
[998000000,598245292],
[999000000,869544707],
[1000000000,698611116],
[1001000000,0]
]

def fact(x):
	ret = facts[x/1000000][1]
	cur = facts[x/1000000][0]
	for i in range(1,len(facts)):
		if x < facts[i][0]:
			cur = facts[i-1][0]
			ret = facts[i-1][1]
			break
	for i in range(cur+1,x+1):
		ret = ret*i%mo
	return ret

def mult(L,R):
	if L/mo != R/mo:
		return 0
	L%=mo
	R%=mo
	if L==0:
		if R==0:
			return 1
		return 0
	elif L==1:
		return fact(R)
	else:
		return fact(R)*pow(fact(L-1),mo-2,mo)%mo

for i in range(T):
	C,P=map(int,raw_input().strip().split(" "))
	if P*2-1>C:
		print 0
	else:
		# P! * H(P+1,C-(2*P-1))
		# = P! * C(C-P+1,P) = (C-P+1)*(C-P+2)*...*(C-2*P+2)
		
		if P >= mo:
			print 0
		else:
			print mult(C-2*P+2,C-P+1) % mo

解法

階乗テーブルは今後も使いまわせるようにしておくかな。
フィボナッチや行列累乗系の作問を考えてたけど、今回色々出てしまったので没。