結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | hipopo |
提出日時 | 2020-04-11 14:00:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 3,219 bytes |
コンパイル時間 | 1,434 ms |
コンパイル使用メモリ | 138,472 KB |
実行使用メモリ | 34,560 KB |
最終ジャッジ日時 | 2024-09-19 00:07:52 |
合計ジャッジ時間 | 3,076 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 32 ms
15,488 KB |
testcase_02 | AC | 18 ms
9,472 KB |
testcase_03 | AC | 68 ms
33,280 KB |
testcase_04 | AC | 21 ms
11,092 KB |
testcase_05 | AC | 6 ms
5,376 KB |
testcase_06 | AC | 28 ms
13,952 KB |
testcase_07 | AC | 47 ms
22,784 KB |
testcase_08 | AC | 34 ms
16,768 KB |
testcase_09 | AC | 53 ms
25,600 KB |
testcase_10 | AC | 71 ms
34,560 KB |
testcase_11 | AC | 23 ms
12,288 KB |
testcase_12 | AC | 6 ms
5,376 KB |
testcase_13 | AC | 26 ms
13,676 KB |
testcase_14 | AC | 9 ms
6,272 KB |
testcase_15 | AC | 30 ms
15,104 KB |
testcase_16 | AC | 72 ms
34,560 KB |
testcase_17 | AC | 71 ms
34,432 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
ソースコード
#include <algorithm> #include <cmath> #include <complex> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> #include <functional> #include <cstring> #include <regex> #include <random> #include <cassert> #include <stack> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, s, n) for (int i = (s); i < (int)(n); i++) #define revrep(i, n) for (int i = (n) - 1; i >= 0; i--) #define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--) #define debug(x) cerr << #x << ": " << x << "\n" #define popcnt(x) __builtin_popcount(x) using ll = long long; using P = pair<int, int>; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class T> istream& operator >>(istream &is, vector<T> &v) { for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i); return is; } template<class T, class U> ostream& operator <<(ostream &os, pair<T, U> p) { cout << '(' << p.first << ", " << p.second << ')'; return os; } template<class T> void print(const vector<T> &v, const string &delimiter) { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; } template<class T> void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); } struct ModInt { static ll mod; ll val; ModInt(ll v = 0) : val(v % mod) {} ModInt operator-() const { return ModInt(val ? mod - val : val); } ModInt &operator+=(ModInt a) { if ((val += a.val) >= mod) val -= mod; return *this; } ModInt &operator-=(ModInt a) { if ((val -= a.val) < 0) val += mod; return *this; } ModInt &operator*=(ModInt a) { val = (__uint128_t(val) * a.val) % mod; return *this; } ModInt &operator/=(ModInt a) { ll u = 1, v = a.val, s = 0, t = mod; while (v) { ll q = t / v; swap(s -= u * q, u); swap(t -= v * q, v); } a.val = (s < 0 ? s + mod : s); val /= t; return (*this) *= a; } ModInt inv() const { return ModInt(1) /= (*this); } bool operator<(ModInt x) const { return val < x.val; } }; ll ModInt::mod = 1e9 + 7; ostream &operator<<(ostream &os, ModInt a) { os << a.val; return os; } ModInt operator+(ModInt a, ModInt b) { return a += b; } ModInt operator-(ModInt a, ModInt b) { return a -= b; } ModInt operator*(ModInt a, ModInt b) { return a *= b; } ModInt operator/(ModInt a, ModInt b) { return a /= b; } ModInt pow(ModInt a, ll e) { ModInt x(1); for (; e > 0; e /= 2) { if (e % 2 == 1) x *= a; a *= a; } return x; } ModInt comb(int n, int k) { ModInt x = 1, y = 1; rep(i, k) { x *= n - i; y *= i + 1; } return x / y; } int main() { int n, p; cin >> n >> p; ModInt a[n]; a[0] = 0; a[1] = 1; repr(i, 2, n) a[i] = ModInt(p) * a[i - 1] + a[i - 2]; ModInt sum[n]; repr(i, 1, n) sum[i] = sum[i - 1] + a[i]; ModInt res; rep(i, n) res += a[i] * sum[i]; cout << res << endl; }