結果
問題 | No.978 Fibonacci Convolution Easy |
ユーザー |
![]() |
提出日時 | 2020-01-31 21:43:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,197 bytes |
コンパイル時間 | 1,487 ms |
コンパイル使用メモリ | 167,936 KB |
実行使用メモリ | 11,012 KB |
最終ジャッジ日時 | 2024-09-18 20:55:05 |
合計ジャッジ時間 | 2,419 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <unsigned Mod> struct Modular { using M = Modular; unsigned v; Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {} M operator-() const { return M() -= *this; } M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; } M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; } M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; } M& operator/=(M r) { return *this *= power(r, Mod - 2); } friend M operator+(M l, M r) { return l += r; } friend M operator-(M l, M r) { return l -= r; } friend M operator*(M l, M r) { return l *= r; } friend M operator/(M l, M r) { return l /= r; } friend bool operator==(M l, M r) { return l.v == r.v; } }; constexpr long long mod = 1e9 + 7; using Mint = Modular<mod>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, p; cin >> n >> p; vector<Mint> a(n); for (int i = 0; i < n; ++i) { if (i < 2) { a[i] = i; } else { a[i] = p * a[i - 1] + a[i - 2]; } } Mint res, sum; for (int i = 0; i < n; ++i) { sum += a[i]; res += sum * a[i]; } cout << res.v << '\n'; }