結果

問題 No.665 Bernoulli Bernoulli
ユーザー 双六双六
提出日時 2020-08-27 23:07:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,390 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 81,536 KB
最終ジャッジ日時 2024-11-08 18:39:05
合計ジャッジ時間 4,183 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
59,136 KB
testcase_01 AC 46 ms
54,016 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, K, con):
		self.fac = [0] * (K + 2)
		self.inv = [0] * (K + 2)
		self.finv = [0] * (K + 2)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1
		self.Bernoulli = [0] * (K + 2)
		self.Bernoulli[0] = 1

		# 前計算
		for i in range(2, K + 2):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

		for i in range(1, K + 1):
			val = 0
			for j in range(i):
				val += self.fac[i + 1] * self.finv[j] * self.finv[i + 1 - j] * self.Bernoulli[j]
				val %= con
			val *= -self.inv[i + 1]
			val %= con
			self.Bernoulli[i] = val

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

	def bekisum(self, n, k):
		res = 0
		for i in range(k + 1):
			res += self.com(k + 1, i) * self.Bernoulli[i] * pow(n, k - i + 1, con)
			res %= con
		res *= self.inv[k + 1]
		res %= con
		return res

#処理内容
def main():
	N, K = getlist()
	C = Combination(N, K, con)
	ans = C.bekisum(N + 1, K)
	print(ans % con)
	# print(C.Bernoulli)




if __name__ == '__main__':
	main()
0