結果
問題 | No.665 Bernoulli Bernoulli |
ユーザー | kimiyuki |
提出日時 | 2018-03-09 23:46:01 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 700 ms / 2,000 ms |
コード長 | 2,082 bytes |
コンパイル時間 | 2,080 ms |
コンパイル使用メモリ | 198,048 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-19 03:56:51 |
合計ジャッジ時間 | 13,413 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 691 ms
5,376 KB |
testcase_03 | AC | 700 ms
5,376 KB |
testcase_04 | AC | 642 ms
5,376 KB |
testcase_05 | AC | 592 ms
5,376 KB |
testcase_06 | AC | 601 ms
5,376 KB |
testcase_07 | AC | 561 ms
5,376 KB |
testcase_08 | AC | 556 ms
5,376 KB |
testcase_09 | AC | 652 ms
5,376 KB |
testcase_10 | AC | 559 ms
5,376 KB |
testcase_11 | AC | 665 ms
5,376 KB |
testcase_12 | AC | 645 ms
5,376 KB |
testcase_13 | AC | 677 ms
5,376 KB |
testcase_14 | AC | 687 ms
5,376 KB |
testcase_15 | AC | 587 ms
5,376 KB |
testcase_16 | AC | 601 ms
5,376 KB |
testcase_17 | AC | 607 ms
5,376 KB |
testcase_18 | AC | 576 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; (i) < int(n); ++ (i)) using ll = long long; using namespace std; ll powmod(ll x, ll y, ll m) { assert (0 <= x and x < m); assert (0 <= y); ll z = 1; for (ll i = 1; i <= y; i <<= 1) { if (y & i) z = z * x % m; x = x * x % m; } return z; } ll modinv(ll x, ll p) { assert (x % p != 0); return powmod(x, p - 2, p); } template <int32_t MOD> int32_t fact(int n) { static vector<int32_t> memo(1, 1); while (n >= memo.size()) { memo.push_back(memo.back() *(int64_t) memo.size() % MOD); } return memo[n]; } template <int32_t PRIME> int32_t inv_fact(int n) { static vector<int32_t> memo(1, 1); while (n >= memo.size()) { memo.push_back(memo.back() *(int64_t) modinv(memo.size(), PRIME) % PRIME); } return memo[n]; } template <int MOD> int choose(int n, int r) { if (n < r) return 0; return fact<MOD>(n) *(ll) inv_fact<MOD>(n - r) % MOD *(ll) inv_fact<MOD>(r) % MOD; } /** * @tparam MOD must be a prime * @note O(n^2) * @see https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E6%95%B0 */ template <int MOD> int bernoulli_number(int i) { static vector<int> dp(1, 1); while (dp.size() <= i) { int n = dp.size(); ll acc = 0; REP (k, n) { acc += choose<MOD>(n + 1, k) *(ll) dp[k] % MOD; } acc %= MOD; (acc *= modinv(n + 1, MOD)) %= MOD; acc = (acc == 0 ? 0 : MOD - acc); dp.push_back(acc); } return dp[i]; } /** * @brief 0^k + 1^k + 2^k + ... + (n - 1)^k */ template <int MOD> int sum_of_pow(ll n, int k) { ll acc = 0; REP (j, k + 1) { acc += choose<MOD>(k + 1, j) *(ll) bernoulli_number<MOD>(j) % MOD *(ll) powmod(n % MOD, k - j + 1, MOD) % MOD; } acc %= MOD; (acc *= modinv(k + 1, MOD)) %= MOD; return acc; } constexpr int MOD = 1e9 + 7; int main() { ll n; int k; cin >> n >> k; int result = sum_of_pow<MOD>(n + 1, k); cout << result << endl; return 0; }