#252596 (C++11) No.665 Bernoulli Bernoulli

• 問題: No.665 Bernoulli Bernoulli
• ユーザー: kriii
• 提出日時: 2018-04-20 00:02:32
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 836 bytes
• コンパイル時間: 363 ms
• コンパイル使用メモリ: 27,528 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-09 11:51:33
• 合計ジャッジ時間: 1,645 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	3 ms; 4,376 KB
testcase_02	AC	3 ms; 4,376 KB
testcase_03	AC	5 ms; 4,376 KB
testcase_04	AC	5 ms; 4,380 KB
testcase_05	AC	5 ms; 4,380 KB
testcase_06	AC	5 ms; 4,380 KB
testcase_07	AC	4 ms; 4,376 KB
testcase_08	AC	4 ms; 4,380 KB
testcase_09	AC	5 ms; 4,376 KB
testcase_10	AC	5 ms; 4,376 KB
testcase_11	AC	5 ms; 4,380 KB
testcase_12	AC	4 ms; 4,376 KB
testcase_13	AC	4 ms; 4,376 KB
testcase_14	AC	5 ms; 4,376 KB
testcase_15	AC	4 ms; 4,380 KB
testcase_16	AC	5 ms; 4,376 KB
testcase_17	AC	4 ms; 4,376 KB
testcase_18	AC	4 ms; 4,376 KB

ソースコード

#include <stdio.h>

const long long mod = 1000000007;
long long N,f[100100],fact[100100]; int K;

long long fpow(long long a, long long p)
{
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

long long inv(long long a)
{
	return fpow(a, mod-2);
}

long long proc()
{
	scanf ("%lld %d",&N,&K);
	N %= mod;
	for (int i=1;i<=K+1;i++) f[i] = (f[i-1] + fpow(i,K)) % mod;

	if (N <= K+1) return f[N];

	long long ans = 0;
	for (int i=1;i<=K+1;i++){
		long long r = f[i] * inv(fact[i] * fact[K+1-i] % mod * (N - i) % mod) % mod;
		if (i % 2 == K % 2) r = mod - r;
		ans = (ans + r) % mod;
	}
	for (int i=0;i<=K+1;i++) ans = ans * (N - i) % mod;

	return ans;
}

int main()
{
	fact[0] = 1;
	for (int i=1;i<100100;i++) fact[i] = fact[i-1] * i % mod;

	printf ("%lld\n",proc());

	return 0;
}