結果
問題 |
No.665 Bernoulli Bernoulli
|
ユーザー |
|
提出日時 | 2018-03-11 20:53:47 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,912 ms / 2,000 ms |
コード長 | 1,334 bytes |
コンパイル時間 | 2,152 ms |
コンパイル使用メモリ | 78,024 KB |
実行使用メモリ | 46,312 KB |
最終ジャッジ日時 | 2024-10-15 00:26:53 |
合計ジャッジ時間 | 40,953 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
ソースコード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().run(); } long MOD = 1_000_000_000 + 7; long[] inv = new long[10002]; long[] B = new long[10001]; { inv[1] = 1; for (int i = 2; i < inv.length; ++i) { inv[i] = MOD - inv[(int) (MOD % i)] * (MOD / i) % MOD; } B[0] = 1; for (int i = 1; i < B.length; ++i) { if (i >= 3 && i % 2 == 1) continue; long C = 1; for (int j = 0; j < i; ++j) { B[i] += (MOD - C * B[j] % MOD) % MOD; B[i] %= MOD; C = C * (i + 1 - j) % MOD * inv[j + 1] % MOD; } B[i] = B[i] * inv[i + 1] % MOD; } } public void run() { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); int k = sc.nextInt(); long ans = 0; long C = 1; for (int i = 0; i <= k; ++i) { ans += C * B[i] % MOD * pow(n, k + 1 - i) % MOD * (i % 2 == 0 ? 1 : MOD - 1) % MOD; ans %= MOD; C = C * (k + 1 - i) % MOD * inv[i + 1] % MOD; } ans = ans * inv[k + 1] % MOD; System.out.println(ans); } long pow(long a, long n) { long ret = 1; a %= MOD; for (; n > 0; n >>= 1, a = a * a % MOD) { if (n % 2 == 1) { ret = ret * a % MOD; } } return ret; } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }