結果

提出番号 2348
提出者 kya
言語 C++
提出日時 2020-03-25 18:43:54
問題名 (15)掛け算フィボナッチ
結果 CE
点数 0%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 CE 0% 0ms 0KB
2 CE 0% 0ms 0KB
3 CE 0% 0ms 0KB
4 CE 0% 0ms 0KB
5 CE 0% 0ms 0KB
6 CE 0% 0ms 0KB
7 CE 0% 0ms 0KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<int mod> struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; }
    ModInt &operator-=(const ModInt &p) { if((x += mod-p.x) >= mod) x -= mod; return *this; }
    ModInt &operator*=(const ModInt &p) { x = (int)(1LL*x*p.x%mod); return *this; }
    ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const{
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
        return ModInt(u);
    }
    ModInt pow(int e){
        long long a = 1, p = x;
        while(e > 0) {
            if(e%2 == 0) {p = (p*p) % mod; e /= 2;}
            else {a = (a*p) % mod; e--;}
        }
        return ModInt(a);
    }
    friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt<mod> &a) {
        long long x;
        is >> x;
        a = ModInt<mod>(x);
        return (is);
    }
};

int main() {
    constexpr int MOD = 1'000'000'007;
    int q;
    cin >> q;
    
    ModInt<MOD> res = 1;
    vector<ModInt<MOD>> a(100100);
    a[0] = a[1] = 1;
    for (int i = 2; i < q; i++) { a[i] = a[i-1] + a[i-2]; res *= a[i]; }
    cout << res << endl;
    return 0;
}