結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | firiexp |
提出日時 | 2020-01-31 23:34:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 2,143 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 97,076 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-10-02 03:32:00 |
合計ジャッジ時間 | 5,837 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 81 ms
11,136 KB |
testcase_01 | AC | 84 ms
11,136 KB |
testcase_02 | AC | 83 ms
11,120 KB |
testcase_03 | AC | 85 ms
11,264 KB |
testcase_04 | AC | 82 ms
11,136 KB |
testcase_05 | AC | 81 ms
11,136 KB |
testcase_06 | AC | 85 ms
11,136 KB |
testcase_07 | AC | 83 ms
11,136 KB |
testcase_08 | AC | 82 ms
11,136 KB |
testcase_09 | AC | 83 ms
11,132 KB |
testcase_10 | AC | 81 ms
11,136 KB |
testcase_11 | AC | 81 ms
11,136 KB |
testcase_12 | AC | 81 ms
11,244 KB |
testcase_13 | AC | 85 ms
11,136 KB |
testcase_14 | AC | 84 ms
11,136 KB |
testcase_15 | AC | 84 ms
11,136 KB |
testcase_16 | AC | 74 ms
11,260 KB |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> #include <limits> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; template<u32 M = 1000000007> struct modint{ u32 val; modint(): val(0){} template<typename T> modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;} modint pow(ll k) const { modint res(1), x(val); while(k){ if(k&1) res *= x; x *= x; k >>= 1; } return res; } template<typename T> modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;} modint inv() const {return pow(M-2);} modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;} modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;} modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;} modint& operator/=(modint a){return (*this) *= a.inv();} modint operator+(modint a) const {return modint(val) +=a;} modint operator-(modint a) const {return modint(val) -=a;} modint operator*(modint a) const {return modint(val) *=a;} modint operator/(modint a) const {return modint(val) /=a;} modint operator-(){return modint(M-val);} bool operator==(const modint a) const {return val == a.val;} bool operator!=(const modint a) const {return val != a.val;} bool operator<(const modint a) const {return val < a.val;} }; using mint = modint<MOD>; int main() { int n = 2000001; int p; cin >> p; vector<mint> v(n+5); v[4] = 1; mint a = mint(p*2), b = mint(p)*mint(p)-mint(2); for (int i = 5; i < n+5; ++i) { v[i] = a*v[i-1]-b*v[i-2]-a*v[i-3]-v[i-4]; } int q; cin >> q; for (int i = 0; i < q; ++i) { int aa; scanf("%d", &aa); printf("%d\n", v[aa].val); } return 0; }