結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー | r1933 |
提出日時 | 2020-02-04 15:46:11 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,492 bytes |
コンパイル時間 | 1,619 ms |
コンパイル使用メモリ | 169,464 KB |
実行使用メモリ | 18,856 KB |
最終ジャッジ日時 | 2024-09-21 07:23:53 |
合計ジャッジ時間 | 3,097 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 36 ms
9,264 KB |
testcase_02 | AC | 21 ms
6,940 KB |
testcase_03 | AC | 84 ms
18,180 KB |
testcase_04 | AC | 23 ms
7,068 KB |
testcase_05 | AC | 6 ms
6,940 KB |
testcase_06 | AC | 31 ms
8,420 KB |
testcase_07 | AC | 55 ms
12,904 KB |
testcase_08 | AC | 40 ms
9,736 KB |
testcase_09 | AC | 63 ms
14,252 KB |
testcase_10 | AC | 87 ms
18,788 KB |
testcase_11 | AC | 26 ms
7,600 KB |
testcase_12 | AC | 6 ms
6,940 KB |
testcase_13 | AC | 30 ms
8,420 KB |
testcase_14 | AC | 10 ms
6,940 KB |
testcase_15 | AC | 35 ms
8,944 KB |
testcase_16 | AC | 87 ms
18,856 KB |
testcase_17 | AC | 86 ms
18,780 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | RE | - |
testcase_20 | AC | 2 ms
6,944 KB |
ソースコード
#include "bits/stdc++.h" #pragma GCC optimize("Ofast") // Begin Header {{{ using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) x.begin(), x.end() #define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i) #define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template <class T> using MaxHeap = priority_queue<T, vector<T>, less<T>>; template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>; inline void input() {} template <class Head, class... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template <class T> inline void input(vector<T> &vec) { for (auto &e: vec) { cin >> e; } } template <class T> inline void input(vector<vector<T>> &mat) { for (auto &vec: mat) { input(vec); } } inline void print() { cout << "\n"; } template <class Head, class... Tail> inline void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) { cout << ' '; } print(forward<Tail>(tail)...); } template <class T> inline ostream& operator<<(ostream &strm, const vector<T> &vec) { static constexpr const char *delim[] = {" ", ""}; for (const auto &e: vec) { strm << e << delim[&e == &vec.back()]; } return strm; } template <class T> inline vector<T> make_v(const T &initValue, size_t sz) { return vector<T>(sz, initValue); } template <class T, class... Args> inline auto make_v(const T &initValue, size_t sz, Args... args) { return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...)); } template <class Func> class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward<Args>(args)...); } }; template <class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template <class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template <class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template <class T> inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } // }}} constexpr intmax_t MOD = intmax_t(1e9) + 7; // Mint {{{ template <intmax_t MOD> class ModInt { intmax_t value; public: inline ModInt(const ModInt& other) noexcept : value(other.value) {} inline ModInt(intmax_t value = 0) noexcept : value((value >= MOD) ? value % MOD : (value < 0) ? (value + MOD) % MOD : value) {} inline ModInt inv() const noexcept { return pow(value, MOD - 2); } inline ModInt& operator+=(const ModInt& other) noexcept { value = (value + other.value) % MOD; return *this; } inline ModInt& operator-=(const ModInt& other) noexcept { value = (MOD + value - other.value) % MOD; return *this; } inline ModInt& operator*=(const ModInt& other) noexcept { value = (value * other.value) % MOD; return *this; } inline ModInt& operator/=(const ModInt& other) noexcept { value = (value * other.inv().value) % MOD; return *this; } inline ModInt operator+(const ModInt& other) noexcept { return ModInt(*this) += other; } inline ModInt operator-(const ModInt& other) noexcept { return ModInt(*this) -= other; } inline ModInt operator*(const ModInt& other) noexcept { return ModInt(*this) *= other; } inline ModInt operator/(const ModInt& other) noexcept { return ModInt(*this) /= other; } inline bool operator==(const ModInt& other) noexcept { return value == *other; } inline bool operator!=(const ModInt& other) noexcept { return value != *other; } template <class int_> explicit inline operator int_() const noexcept { return static_cast<int_>(value); } friend ostream& operator<<(ostream &os, ModInt other) noexcept { os << other.value; return os; } friend istream& operator>>(istream &is, ModInt& other) noexcept { is >> other.value; return is; } static constexpr inline ModInt pow(intmax_t n, intmax_t p) noexcept { intmax_t ret = 1; for (; p > 0; p >>= 1) { if (p & 1) ret = (ret * n) % MOD; n = (n * n) % MOD; } return ret; } }; using Mint = ModInt<MOD>; // }}} signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); var(size_t, N); var(Mint, p); if (N == 0) { return print(0), 0; } else if (N == 2) { return print(1), 1; } vector<Mint> a(N + 1); a[1] = 0; a[2] = 1; reps(i, 3, N) { a[i] = p * a[i - 1] + a[i - 2]; } Mint res = 0, cumSum = 0; reps(i, 1, N) { cumSum += a[i]; res += a[i] * cumSum; } print(res); return 0; }