結果
問題 | No.665 Bernoulli Bernoulli |
ユーザー | imulan |
提出日時 | 2018-03-10 03:00:12 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 272 ms / 2,000 ms |
コード長 | 1,488 bytes |
コンパイル時間 | 1,825 ms |
コンパイル使用メモリ | 164,148 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-19 13:41:34 |
合計ジャッジ時間 | 6,228 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,248 KB |
testcase_02 | AC | 272 ms
5,376 KB |
testcase_03 | AC | 253 ms
5,376 KB |
testcase_04 | AC | 240 ms
5,376 KB |
testcase_05 | AC | 247 ms
5,376 KB |
testcase_06 | AC | 229 ms
5,376 KB |
testcase_07 | AC | 220 ms
5,376 KB |
testcase_08 | AC | 221 ms
5,376 KB |
testcase_09 | AC | 246 ms
5,376 KB |
testcase_10 | AC | 222 ms
5,376 KB |
testcase_11 | AC | 249 ms
5,376 KB |
testcase_12 | AC | 241 ms
5,376 KB |
testcase_13 | AC | 260 ms
5,376 KB |
testcase_14 | AC | 261 ms
5,376 KB |
testcase_15 | AC | 223 ms
5,376 KB |
testcase_16 | AC | 233 ms
5,376 KB |
testcase_17 | AC | 227 ms
5,376 KB |
testcase_18 | AC | 219 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second #define dbg(x) cout<<#x" = "<<((x))<<endl template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} const ll mod = 1e9+7; ll mod_pow(ll x, ll n){ ll ret = 1; while(n){ if(n&1) (ret*=x)%=mod; (x*=x)%=mod; n>>=1; } return ret; } ll mod_inv(ll x){ return mod_pow(x, mod-2); } const int N = 10010; ll f[N]; ll invf[N]; ll C(ll n, ll r){ ll ret = f[n]; (ret*=invf[r])%=mod; (ret*=invf[n-r])%=mod; return ret; } ll b[N]; void B(int k){ b[0] = 1; for(int i=1; i<=k; ++i){ b[i] = 0; rep(j,i) (b[i] += C(i+1,j)*b[j]) %= mod; (b[i] *= mod_inv(i+1)) %= mod; b[i] = (mod - b[i])%mod; } } int main(){ f[0] = 1; for(int i=1; i<N; ++i) f[i] = (f[i-1]*i)%mod; rep(i,N) invf[i] = mod_inv(f[i]); ll n; int k; cin >>n >>k; n%=mod; B(k+1); ll ans = 0; rep(i,k+1){ ll add = mod_pow(n+1,k+1-i); (add *= C(k+1,i)) %= mod; (add *= b[i]); (ans += add) %= mod; } (ans*=mod_inv(k+1))%=mod; cout << ans << endl; return 0; }