yukicoder : No.1327 グラフの数え上げ

うーん。
https://yukicoder.me/problems/no/1327

問題

整数Nが与えられる。
N頂点M無向辺のグラフのうち、単純かつ連結なものの数をF(N,M)とする。
sum*1を1000000007で割った余りを答えよ。

解法

以下良い解き方ではないが、本番中の動きを記載する。
サンプルを見ると解が(N-1)になりそうだがそうでもない。

Nが小さいケースを実際に生成して見ると、(-1)^(N-1)*(N-1)!が解となることが推測できる。

• N＞1000000008の時は0
• それ以外の場合、(N-1)!を求めないといけないが、愚直に(N-1)回掛け算すると間に合わないので、値を埋め込んでしまおう。

N=input()

def fact(N):
	facts=[
	[0,1],
	[10000000,682498929],
	[20000000,491101308],
	[30000000,76479948],
	(略)
	[990000000,847549272],
	[1000000000,698611116],
	[1001000000,0]
	]
	
	cur = 0
	ret = 1
	
	for f in facts:
		if N >= f[0]:
			cur = f[0]
			ret = f[1]
	
	for i in range(cur+1,N+1):
		ret = ret * i % 1000000007
	return ret


if len(N)>10:
	print(0)
else:
	N = int(N)
	if N>=1000000008:
		print(0)
	else:
		v = fact(N-1)
		if N % 2 == 0:
			v = 1000000007-v
		print(v)

まとめ

サンプルケースが絶妙な問題。

*1:-1)^M*F(N,M