結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | hrbt__ |
提出日時 | 2020-03-09 19:11:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 2,508 bytes |
コンパイル時間 | 1,867 ms |
コンパイル使用メモリ | 166,532 KB |
実行使用メモリ | 34,500 KB |
最終ジャッジ日時 | 2024-04-26 06:20:55 |
合計ジャッジ時間 | 4,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 64 ms
15,472 KB |
testcase_02 | AC | 34 ms
9,344 KB |
testcase_03 | AC | 153 ms
33,236 KB |
testcase_04 | AC | 42 ms
10,992 KB |
testcase_05 | AC | 11 ms
6,940 KB |
testcase_06 | AC | 55 ms
13,672 KB |
testcase_07 | AC | 99 ms
22,576 KB |
testcase_08 | AC | 70 ms
16,548 KB |
testcase_09 | AC | 115 ms
25,492 KB |
testcase_10 | AC | 157 ms
34,420 KB |
testcase_11 | AC | 48 ms
12,044 KB |
testcase_12 | AC | 10 ms
6,940 KB |
testcase_13 | AC | 54 ms
13,632 KB |
testcase_14 | AC | 17 ms
6,940 KB |
testcase_15 | AC | 62 ms
15,084 KB |
testcase_16 | AC | 157 ms
34,500 KB |
testcase_17 | AC | 158 ms
34,448 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct ModInt { using M = ModInt; static vector<M> fact, finv; static long long MOD; long long v; // normalize: [-MOD, MOD**2] -> [0, MOD) ModInt(const long long _v = 0) : v((_v < 0) ? _v % MOD + MOD : _v % MOD) {} M operator+(const M& x) const { return M(v + x.v); } M operator-(const M& x) const { return M(v - x.v); } M operator*(const M& x) const { return M(v * x.v); } M operator/(const M& x) const { return M(v * x.inv().v); } M& operator+=(const M& x) { return *this = *this + x; } M& operator-=(const M& x) { return *this = *this - x; } M& operator*=(const M& x) { return *this = *this * x; } M& operator/=(const M& x) { return *this = *this / x; } bool operator==(const M& x) const { return v == x.v; } bool operator!=(const M& x) const { return v != x.v; } friend istream& operator>>(istream& input, M& x) { return input >> x.v, x = M(x), input; } friend ostream& operator<<(ostream& output, const M& x) { return output << x.v; } inline M pow(long long n) const { M x(v), res(1); while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } inline M inv() const { return this->pow(MOD - 2); } static void build(int n) { fact.assign(n + 1, 1); for (int i = 1; i < n + 1; i++) fact[i] = fact[i - 1] * M(i); finv.assign(n + 1, fact[n].inv()); for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * M(i); } static M comb(int n, int k) { if (n < k || k < 0) return M(0); return fact[n] * finv[n - k] * finv[k]; } static M extgcd(int a, int b, int& x, int& y) { M d(a); if (b) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } }; vector<ModInt> ModInt::fact = vector<ModInt>(); vector<ModInt> ModInt::finv = vector<ModInt>(); long long ModInt::MOD = 1e9 + 7; int main() { int n; ModInt p; cin >> n >> p; vector<ModInt> a(n, 0); a[1] = 1; for (int i = 2; i < n; i++) { a[i] = p * a[i - 1] + a[i - 2]; } vector<ModInt> cumsum(n + 1, 0); for (int i = 0; i < n; i++) { cumsum[i + 1] = cumsum[i] + a[i]; } ModInt ans = 0; for (int i = 0; i < n; i++) { ans += a[i] * cumsum[i + 1]; } cout << ans << endl; }