結果

問題 No.665 Bernoulli Bernoulli
ユーザー tomatoma
提出日時 2020-03-03 01:16:02
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 1,083 bytes
コンパイル時間 1,472 ms
コンパイル使用メモリ 165,320 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-04 00:24:41
合計ジャッジ時間 2,745 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 4 ms
4,380 KB
testcase_03 AC 18 ms
4,376 KB
testcase_04 AC 18 ms
4,376 KB
testcase_05 AC 16 ms
4,376 KB
testcase_06 AC 17 ms
4,380 KB
testcase_07 AC 17 ms
4,376 KB
testcase_08 AC 17 ms
4,380 KB
testcase_09 AC 18 ms
4,376 KB
testcase_10 AC 17 ms
4,380 KB
testcase_11 AC 18 ms
4,380 KB
testcase_12 AC 18 ms
4,380 KB
testcase_13 AC 19 ms
4,380 KB
testcase_14 AC 18 ms
4,384 KB
testcase_15 AC 17 ms
4,376 KB
testcase_16 AC 18 ms
4,380 KB
testcase_17 AC 17 ms
4,376 KB
testcase_18 AC 17 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;

// from kmjp
ll mo = 1000000007;
ll P[101010];
ll fact[101010];

ll modpow(ll a, ll n = mo - 2) {
    ll r = 1; a %= mo;
    while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a%mo, n >>= 1;
    return r;
}

ll solve(ll N, ll K) {
    ll i, j, k, l, r, x, y; string s;

    fact[0] = 1;
    for (i = 1; i <= K + 1; i++) {
        (P[i] = modpow(i, K) + P[i - 1]) %= mo;
        fact[i] = fact[i - 1] * i%mo;
    }


    if (N <= K + 1) return P[N];
    N = N % mo + mo;

    ll ret = 0;
    ll A = 1;
    for (i = 0; i <= K + 1; i++) A = A * (N - i) % mo;

    for (i = 0; i <= K + 1; i++) {
        ll v = P[i] * A%mo*modpow(N - i) % mo;
        ll w = fact[K + 1 - i] * fact[i] % mo;
        v = v * modpow(w) % mo;

        if (i % 2 != (K + 1) % 2) ret = (ret + mo - v) % mo;
        else ret = (ret + v) % mo;
    }
    return ret;
}

int main()
{
    ll A, K;
    cin >> A >> K;
    cout << solve(A, K) << endl;
    return 0;
}
0