結果

問題 No.665 Bernoulli Bernoulli
ユーザー ミドリムシ+
提出日時 2018-03-09 23:23:25
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 347 ms
コード長 1,875 Byte
コンパイル時間 515 ms
使用メモリ 3,252 KB
最終ジャッジ日時 2019-10-06 17:46:54

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 34 ms
3,248 KB
sample2.txt AC 35 ms
3,248 KB
sample3.txt AC 347 ms
3,248 KB
sample4.txt AC 343 ms
3,248 KB
test1.txt AC 324 ms
3,252 KB
test2.txt AC 306 ms
3,248 KB
test3.txt AC 301 ms
3,248 KB
test4.txt AC 293 ms
3,252 KB
test5.txt AC 294 ms
3,248 KB
test6.txt AC 330 ms
3,252 KB
test7.txt AC 293 ms
3,248 KB
test8.txt AC 337 ms
3,248 KB
test9.txt AC 329 ms
3,252 KB
test10.txt AC 340 ms
3,252 KB
test11.txt AC 342 ms
3,248 KB
test12.txt AC 301 ms
3,248 KB
test13.txt AC 313 ms
3,252 KB
test14.txt AC 319 ms
3,252 KB
test15.txt AC 296 ms
3,252 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