結果

問題 No.665 Bernoulli Bernoulli
ユーザー rlangevinrlangevin
提出日時 2023-10-27 00:41:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 233 ms / 2,000 ms
コード長 1,158 bytes
コンパイル時間 5,245 ms
コンパイル使用メモリ 311,692 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 12:35:32
合計ジャッジ時間 10,810 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 232 ms
6,816 KB
testcase_01 AC 232 ms
6,816 KB
testcase_02 AC 232 ms
6,940 KB
testcase_03 AC 232 ms
6,940 KB
testcase_04 AC 232 ms
6,940 KB
testcase_05 AC 231 ms
6,940 KB
testcase_06 AC 232 ms
6,944 KB
testcase_07 AC 232 ms
6,944 KB
testcase_08 AC 232 ms
6,940 KB
testcase_09 AC 232 ms
6,940 KB
testcase_10 AC 232 ms
6,944 KB
testcase_11 AC 232 ms
6,944 KB
testcase_12 AC 233 ms
6,940 KB
testcase_13 AC 232 ms
6,940 KB
testcase_14 AC 232 ms
6,944 KB
testcase_15 AC 232 ms
6,944 KB
testcase_16 AC 233 ms
6,940 KB
testcase_17 AC 232 ms
6,944 KB
testcase_18 AC 232 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
using mint = modint1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main()
{
    ll N, K;
    cin >> N >> K;
    int M = 20005;
    vector<mint> fact(M + 1, 1), invfact(M + 1, 1);
    for (int i = 1; i <= M; i++)
    {
        fact[i] = fact[i - 1] * i;
    }
    invfact[M] = fact[M].inv();
    for (int i = M - 1; i >= 0; i--)
    {
        invfact[i] = invfact[i + 1] * (i + 1);
    }

    vector<mint> B(M);
    B[0] = 1;
    B[1] = -((mint)2).inv();
    for (int i = 2; i < M; i += 2)
    {
        mint temp = -B[1];
        for (int k = 0; k <= i; k += 2)
        {
            temp -= invfact[i + 1] * fact[i] * fact[i + 1] * invfact[k] * invfact[i + 1 - k] * B[k];
        }
        B[i] = temp;
    }
    mint ans = 0;
    mint v = ((mint)(N + 1)).pow(K + 1);
    mint inv = ((mint)(N + 1)).inv();
    rep(i, K + 1)
    {
        ans += fact[K + 1] * invfact[i] * invfact[K + 1 - i] * B[i] * v;
        v *= inv;
    }
    ans *= ((mint)(K + 1)).inv();
    cout << ans.val() << endl;
}
0