結果
問題 | No.665 Bernoulli Bernoulli |
ユーザー | 👑 はまやんはまやん |
提出日時 | 2018-03-14 17:32:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 3,117 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 171,216 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-06 00:37:25 |
合計ジャッジ時間 | 2,479 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 4 ms
5,376 KB |
testcase_03 | AC | 11 ms
5,376 KB |
testcase_04 | AC | 10 ms
5,376 KB |
testcase_05 | AC | 9 ms
5,376 KB |
testcase_06 | AC | 10 ms
5,376 KB |
testcase_07 | AC | 9 ms
5,376 KB |
testcase_08 | AC | 9 ms
5,376 KB |
testcase_09 | AC | 10 ms
5,376 KB |
testcase_10 | AC | 9 ms
5,376 KB |
testcase_11 | AC | 11 ms
5,376 KB |
testcase_12 | AC | 10 ms
5,376 KB |
testcase_13 | AC | 11 ms
5,376 KB |
testcase_14 | AC | 10 ms
5,376 KB |
testcase_15 | AC | 10 ms
5,376 KB |
testcase_16 | AC | 10 ms
5,376 KB |
testcase_17 | AC | 10 ms
5,376 KB |
testcase_18 | AC | 9 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- struct LagrangePolynomial { int n; int mod; vector<int> v; vector<int> fac, inv, finv; void init(int _n, int mo = 1000000007) { n = _n; mod = mo; fac.resize(n + 1); fac[0] = 1; rep(i, 1, n + 1) fac[i] = (1LL * fac[i - 1] * i) % mod; inv.resize(n + 1); inv[1] = 1; rep(i, 2, n + 1) inv[i] = (1LL * inv[mod % i] * (mod - mod / i)) % mod; finv.resize(n + 1); finv[0] = 1; rep(i, 1, n + 1) finv[i] = (1LL * finv[i - 1] * inv[i]) % mod; } int modpow(int x, int n) { int res = 1; while (n) { if (n & 1) res = (1LL * res * x) % mod; x = (1LL * x * x) % mod; n >>= 1; } return res; } int modinv(int a) { return modpow(a, mod - 2); } void add(int y) { v.push_back(y); } int get(ll x) { if (x <= n) return v[x]; assert(n + 1 <= v.size()); int num = 1; rep(i, 0, n + 1) num = (1LL * num * ((x - i) % mod)) % mod; int res = 0; rep(i, 0, n + 1) { int d = (1LL * v[i] * num) % mod; d = (1LL * d * modinv((x - i) % mod)) % mod; d = (1LL * d * finv[i]) % mod; d = (1LL * d * finv[n-i]) % mod; if ((n - i) & 1) d = mod - d; res = (res + d) % mod; } return res; } // for 1^k + 2^k + ... + n^k (mod10^9+7) void initexpsum(int k, int mo = 1000000007) { assert(k <= 2000000); init(k + 1, mo); int sm = 0; rep(i, 0, k + 2) { sm = (sm + modpow(i, k)) % mod; add(sm); } } }; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ LagrangePolynomial lp; ll N, K; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; lp.initexpsum(K); cout << lp.get(N) << endl; }