結果

問題 No.665 Bernoulli Bernoulli
コンテスト
ユーザー ojisan_IT
提出日時 2018-04-11 18:03:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 515 ms / 2,000 ms
コード長 2,452 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 177,904 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-26 21:13:26
合計ジャッジ時間 10,509 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV ll(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
// IT 5000兆　欲しい
/* Coding space */
unordered_map<int,int> Inv;
inline ll InvMod(ll n){
  if(Inv.count(n))  return Inv[n];
  return Inv[n] = pow(n, DIV - 2,DIV);
}

class FermatCombination{
public:
  vector<ll> factrial; // 階乗
  vector<ll> inverse; // 逆元
  FermatCombination(int size){
    factrial.resize(size+1);
    inverse.resize(size+1);
    factrial[0] = 1;
    inverse[0] = 1;
    for(int i = 1; i < size+1; i++){
      factrial[i] = factrial[i-1] * i % DIV;
      inverse[i] = pow(factrial[i],DIV-2,DIV);
    }
  }
  ll combination(int n, int k){
    if(n < k) return 0; 
    return factrial[n]* inverse[k] % DIV * inverse[n - k] % DIV;
  }
  ll permutation(int n, int k){
    if(n < k) return 0; 
    return factrial[n] * inverse[n-k] % DIV;
  }
  ll multi_choose(int n, int k){
    if(n == 0 && k == 0) return 1;
    else return combination(n+k-1,k);
  }
};
FermatCombination fc(10006);

ll k,n;

ll B[10005] = {};
bool used[10005] = {};
ll Bernoulli(int x){
  //cerr <<x << endl;
  if(x == 0){
    B[0] = 1;
    return 1;
  }
  if(used[x])  return B[x];
  used[x] = 1;
  ll ret = 0;
  rep(i,x){
    ret += (fc.combination(x+1,i) * Bernoulli(i))%DIV;
    ret %= DIV;
  }
  ret *= -InvMod(x+1);
  while(ret < 0){
    ret += DIV;
    ret %= DIV;
  }
  B[x] = ret;
  return ret;
}

int main() {
  cin >> n >> k;
  n %= DIV;
  ll s = 0;
  rep(j,k+1){
    //cerr << s << " " << fc.combination(k+1,j) << " " << Bernoulli(j) << " " << pow(n+1,k-j+1,DIV) <<endl;
    s += ((((fc.combination(k+1,j) * Bernoulli(j)) % DIV)*pow(n+1,k-j+1,DIV))%DIV);
    s %= DIV;
    //cerr << s << endl;
  }
  ll ans = (InvMod(k+1)*s)%DIV;
  ans %= DIV;
  cout << ans << endl;
}
0