結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー 双六
提出日時 2020-08-27 23:12:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,578 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 81,920 KB
最終ジャッジ日時 2024-11-08 18:51:59
合計ジャッジ時間 3,871 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1 -- * 1
other -- * 15
権限があれば一括ダウンロードができます

ソースコード

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
		self.power = [1] * (K + 2)

		for i in range(1, K + 2):
			self.power[i] = (self.power[i - 1] * (N + 1)) % con

		# 前計算
		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] * self.power[k - i + 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