結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー toma
提出日時 2020-03-03 01:16:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 1,083 bytes
コンパイル時間 1,436 ms
コンパイル使用メモリ 167,388 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 21:27:35
合計ジャッジ時間 2,358 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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