結果
問題 |
No.665 Bernoulli Bernoulli
|
ユーザー |
|
提出日時 | 2020-03-03 01:16:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 1,436 ms |
コンパイル使用メモリ | 167,388 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 21:27:35 |
合計ジャッジ時間 | 2,358 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 15 |
ソースコード
#include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; // from kmjp ll mo = 1000000007; ll P[101010]; ll fact[101010]; ll modpow(ll a, ll n = mo - 2) { ll r = 1; a %= mo; while (n) r = r * ((n % 2) ? a : 1) % mo, a = a * a%mo, n >>= 1; return r; } ll solve(ll N, ll K) { ll i, j, k, l, r, x, y; string s; fact[0] = 1; for (i = 1; i <= K + 1; i++) { (P[i] = modpow(i, K) + P[i - 1]) %= mo; fact[i] = fact[i - 1] * i%mo; } if (N <= K + 1) return P[N]; N = N % mo + mo; ll ret = 0; ll A = 1; for (i = 0; i <= K + 1; i++) A = A * (N - i) % mo; for (i = 0; i <= K + 1; i++) { ll v = P[i] * A%mo*modpow(N - i) % mo; ll w = fact[K + 1 - i] * fact[i] % mo; v = v * modpow(w) % mo; if (i % 2 != (K + 1) % 2) ret = (ret + mo - v) % mo; else ret = (ret + v) % mo; } return ret; } int main() { ll A, K; cin >> A >> K; cout << solve(A, K) << endl; return 0; }