結果

問題 No.665 Bernoulli Bernoulli
ユーザー ミドリムシ+
提出日時 2018-03-09 23:23:25
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 360 ms
コード長 1,875 Byte
コンパイル時間 546 ms
使用メモリ 8,916 KB
最終ジャッジ日時 2019-07-09 03:38:39

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 34 ms
8,916 KB
sample2.txt AC 37 ms
6,872 KB
sample3.txt AC 359 ms
6,872 KB
sample4.txt AC 357 ms
6,868 KB
test1.txt AC 339 ms
6,872 KB
test2.txt AC 323 ms
6,872 KB
test3.txt AC 316 ms
6,872 KB
test4.txt AC 311 ms
6,868 KB
test5.txt AC 308 ms
6,868 KB
test6.txt AC 345 ms
6,868 KB
test7.txt AC 311 ms
6,872 KB
test8.txt AC 351 ms
6,868 KB
test9.txt AC 343 ms
6,868 KB
test10.txt AC 356 ms
6,868 KB
test11.txt AC 360 ms
6,868 KB
test12.txt AC 318 ms
6,872 KB
test13.txt AC 327 ms
6,868 KB
test14.txt AC 318 ms
6,872 KB
test15.txt AC 313 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long power(long base, int exponent){
    if(exponent % 2){
        return power(base, exponent - 1) * base % long(1e9 + 7);
    }else if(exponent){
        long root_ans = power(base, exponent / 2);
        return root_ans * root_ans % long(1e9 + 7);
    }else{
        return 1;
    }
}

vector<long> factorial{1};
vector<long> factorial_inverse_element{1};

long combination(int n, int r){
    return factorial[n] * factorial_inverse_element[r] % long(1e9 + 7) * factorial_inverse_element[n - r] % long(1e9 + 7);
}

int main(){
    long n;
    int k;
    cin >> n >> k;
    for(long i = 1; i < 1e5; i++){
        factorial.push_back(factorial.back() * i % long(1e9 + 7));
        factorial_inverse_element.push_back(power(factorial.back(), 1e9 + 5));
    }
    long bernoulli_numbers[k + 1];
    bernoulli_numbers[0] = 1;
    for(int i = 1; i <= k; i++){
        bernoulli_numbers[i] = 0;
        for(int j = 0; j < i; j++){
            if(j % 2){
                bernoulli_numbers[i] += bernoulli_numbers[j] * combination(i + 1, j) % long(1e9 + 7);
            }else{
                bernoulli_numbers[i] += long(1e9 + 7) - bernoulli_numbers[j] * combination(i + 1, j) % long(1e9 + 7);
            }
        }
        bernoulli_numbers[i] %= long(1e9 + 7);
        if(i % 2){
            bernoulli_numbers[i] *= long(1e9 + 7) - power(combination(i + 1, i), 1e9 + 5);
        }else{
            bernoulli_numbers[i] *= power(combination(i + 1, i), 1e9 + 5);
        }
        bernoulli_numbers[i] %= long(1e9 + 7);
    }
    long ans = 0;
    for(int i = 0; i <= k; i++){
        ans += combination(k + 1, i) * bernoulli_numbers[i] % long(1e9 + 7) * power(n % long(1e9 + 7), k + 1 - i) % long(1e9 + 7);
    }
    cout << ans % long(1e9 + 7) * power(k + 1, 1e9 + 5) % long(1e9 + 7) << endl;
}
0