結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー どらら
提出日時 2018-03-12 22:08:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 397 ms / 2,000 ms
コード長 2,037 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 169,864 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 13:51:17
合計ジャッジ時間 10,440 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

template<ll MOD, ll MX>
class SumOfPower {
  ll fact[MX];
  ll invfact[MX];
  ll B[MX];
  
  ll extgcd(ll a, ll b, ll &x, ll &y){
    ll d = a;
    if(b!=0){
      d = extgcd(b,a%b,y,x);
      y -= (a/b)*x;
    }else{
      x = 1; y = 0;
    }
    return d;
  }
  
  ll mod_inverse(ll a, ll m){
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m)%m;
  }
  
  ll mod_pow(ll x, ll n, ll mod){
    if(n==0) return 1;
    ll res = mod_pow(x * x % mod, n / 2, mod);
    if(n & 1) res = res * x % mod;
    return res;
  }
  
  ll mod_comb(ll n, ll k, ll p){
    if(n<0 || k<0 || n<k) return 0;
    return (((fact[n] * invfact[k]) % MOD) * invfact[n-k]) % MOD;
  }
  
  void comb_init(){
    fact[0] = fact[1] = 1;
    for(ll i=2; i<MX; i++) fact[i] = (fact[i-1] * i) % MOD;
    invfact[0] = invfact[1] = 1;
    for(ll i=2; i<MX; i++) invfact[i] = mod_pow(fact[i], MOD-2, MOD);
  }

  void calc_bernoulli(){
    B[0] = 1;
    for(int i=1; i<MX; i++){
      ll sum = 0;
      rep(j,i){
        sum += (mod_comb(i+1,j,MOD) * B[j]) % MOD;
        sum %= MOD;
      }
      sum *= mod_inverse(i+1, MOD);
      sum %= MOD;
      sum *= -1;
      sum += MOD;
      B[i] = sum;
    }
  }
  
public:
  SumOfPower(){
    comb_init();
    calc_bernoulli();
  }

  // (1^k + ... + n^k) mod MOD, k<MX
  ll solve(ll n, ll k){
    n++;
    ll ret = 0;
    for(int j=0; j<=k; j++){
      ll x = mod_comb(k+1,j, MOD);
      x *= B[j];
      x %= MOD;
      x *= mod_pow(n%MOD, k-j+1, MOD);
      x %= MOD;
      ret += x;
      ret %= MOD;
    }
    ret *= mod_inverse(k+1, MOD);
    ret %= MOD;
    return ret;
  }
};

int main(){
  ll n, k;
  cin >> n >> k;
  
  SumOfPower<1000000007LL,10005> sop;
  
  cout << sop.solve(n, k) << endl;

  return 0;
}
0