結果

問題 No.665 Bernoulli Bernoulli
ユーザー sakaki_tohrusakaki_tohru
提出日時 2021-02-26 18:35:04
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 2,760 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-04-10 08:45:55
合計ジャッジ時間 3,779 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,776 KB
testcase_01 AC 31 ms
11,776 KB
testcase_02 AC 151 ms
12,032 KB
testcase_03 AC 154 ms
12,160 KB
testcase_04 AC 156 ms
12,032 KB
testcase_05 AC 150 ms
12,032 KB
testcase_06 AC 151 ms
12,032 KB
testcase_07 AC 149 ms
12,032 KB
testcase_08 AC 145 ms
12,032 KB
testcase_09 AC 157 ms
12,032 KB
testcase_10 AC 145 ms
12,032 KB
testcase_11 AC 157 ms
12,032 KB
testcase_12 AC 155 ms
12,032 KB
testcase_13 AC 157 ms
12,032 KB
testcase_14 AC 158 ms
12,032 KB
testcase_15 AC 143 ms
12,032 KB
testcase_16 AC 151 ms
12,032 KB
testcase_17 AC 148 ms
12,032 KB
testcase_18 AC 150 ms
12,032 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

num=[
1,2,4,6,12,
24,36,48,60,120,
180,240,360,720,840,
1260,1680,2520,5040,7560,
10080,15120,20160,25200,27720,
45360,50400,55440,83160,110880,
166320,221760,277200,332640,498960,
554400,665280,720720,1081080,1441440,
2162160,2882880,3603600,4324320,6486480,
7207200,8648640,10810800,14414400,17297280,
21621600,32432400,36756720,43243200,61261200,
73513440,110270160,122522400,147026880,183783600,
245044800,294053760,367567200,551350800,698377680,
735134400,1102701600,1396755360,2095133040,2205403200,
2327925600,2793510720,3491888400,4655851200,5587021440,
6983776800,10475665200,13967553600,20951330400,27935107200,
41902660800,48886437600,64250746560,73329656400,80313433200,
97772875200,128501493120,146659312800,160626866400,240940299600,
293318625600,321253732800,481880599200,642507465600,963761198400,
1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,
3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,
9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,
32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,
93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,
288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,
1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,
2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,
10108248702552000,12129898443062400,18194847664593600,20216497405104000,24259796886124800,
30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,
74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,
299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000
]

MOD=1000000007
Mod=1000000007

def prime_factor(n):
	ret=[]
	i=2
	while i*i<=n:
		tmp = 0
		while n % i == 0 :
			tmp+=1
			n /= i
		if tmp!=0:
			ret.append([i,tmp])
		i+=1
	if n != 1:
		ret.append([n,1])
	return ret

def divisor_num(N):
    pf = prime_factor(N)
    ret = 1
    for i in range (0,len(pf)):
        ret *= (pf[i][1] + 1);
    
    return ret;

def getNum(N):
	res=0
	for i in range (0,130):
		if N>=num[i]:
			res=num[i]
	return divisor_num(res)

def Inv(x):
    return pow((x + Mod) % Mod, Mod - 2,Mod)

N,k=map(int,input().split())
#N=int(input())
#k=getNum(N)

js=[0]*100000

res=1
res2=1
js[0]=1

for i in range(1,k+3):
	js[i]=(js[i-1]*i)%MOD
	res=(res*(N-i)+Mod)%MOD
	if i!=N:
		res2=(res2*(N-i))%MOD

now=0
ans=0

for i in range(1,k+3):
	now=(now+pow(i,k,MOD))%MOD
	A=0
	if i!=N:
		A=res * Inv(N - i) % Mod
	else:
		A=res2
	B=js[i-1]*js[k+2-i]%MOD
	if (k+2-i)%2==1:
		B=(-B)%MOD
	ans=(ans+now*A*Inv(B))%MOD;

print(ans%MOD)
0