#486052 (C++11) No.194 フィボナッチ数列の理解(1)

• 問題: No.194 フィボナッチ数列の理解(1)
• ユーザー: 🍮かんプリン
• 提出日時: 2020-05-23 01:51:08
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 197 ms / 5,000 ms
• コード長: 6,945 bytes
• コンパイル時間: 1,589 ms
• コンパイル使用メモリ: 169,740 KB
• 実行使用メモリ: 19,072 KB
• 最終ジャッジ日時: 2024-04-15 22:48:28
• 合計ジャッジ時間: 4,711 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	197 ms; 5,376 KB
testcase_03	AC	9 ms; 5,376 KB
testcase_04	AC	52 ms; 5,376 KB
testcase_05	AC	39 ms; 5,376 KB
testcase_06	AC	54 ms; 5,376 KB
testcase_07	AC	106 ms; 5,376 KB
testcase_08	AC	6 ms; 5,376 KB
testcase_09	AC	77 ms; 5,376 KB
testcase_10	AC	20 ms; 5,376 KB
testcase_11	AC	21 ms; 5,376 KB
testcase_12	AC	41 ms; 5,376 KB
testcase_13	AC	12 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	144 ms; 5,376 KB
testcase_16	AC	117 ms; 5,376 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	AC	121 ms; 5,376 KB
testcase_19	AC	189 ms; 5,376 KB
testcase_20	AC	3 ms; 5,376 KB
testcase_21	AC	18 ms; 19,072 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	4 ms; 5,376 KB
testcase_24	AC	10 ms; 10,624 KB
testcase_25	AC	9 ms; 9,984 KB
testcase_26	AC	10 ms; 9,728 KB
testcase_27	AC	10 ms; 11,520 KB
testcase_28	AC	5 ms; 5,376 KB
testcase_29	AC	15 ms; 17,536 KB
testcase_30	AC	190 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	35 ms; 5,376 KB
testcase_33	AC	64 ms; 5,376 KB
testcase_34	AC	46 ms; 5,376 KB
testcase_35	AC	34 ms; 5,376 KB
testcase_36	AC	130 ms; 5,376 KB
testcase_37	AC	6 ms; 5,376 KB
testcase_38	AC	159 ms; 5,376 KB
testcase_39	AC	41 ms; 5,376 KB

ソースコード

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.05.23 01:51:04
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

constexpr int MOD = 1e9 + 7;
struct mint {
private:
    long long x;
public:
    mint(long long x = 0) : x((MOD + x) % MOD) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= MOD;
        }
        this->x = z;
    }
    mint &operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator-=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator*=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint &operator/=(const mint &a) {
        long long n = MOD - 2;
        mint u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
};
template < class T >
struct Matrix {
    std::vector< std::vector< T > > A;
    Matrix() {}
    Matrix(size_t n, size_t m) : A(n, std::vector< T >(m, 0)) {}
    Matrix(size_t n) : A(n, std::vector< T >(n, 0)){};
    size_t height() const {
        return (A.size());
    }
    size_t width() const {
        return (A[0].size());
    }
    inline const std::vector< T > &operator[](int k) const {
        return (A.at(k));
    }
    inline std::vector< T > &operator[](int k) {
        return (A.at(k));
    }
    static Matrix I(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++) mat[i][i] = 1;
        return (mat);
    }
    Matrix &operator+=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];
        return (*this);
    }
    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];
        return (*this);
    }
    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        std::vector< std::vector< T > > C(n, std::vector< T >(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }
    Matrix operator+(const Matrix &B) const {
        return (Matrix(*this) += B);
    }
    Matrix operator-(const Matrix &B) const {
        return (Matrix(*this) -= B);
    }
    Matrix operator*(const Matrix &B) const {
        return (Matrix(*this) *= B);
    }
    friend std::ostream &operator<<(std::ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }
    // 行列式
    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0) idx = j;
            }
            if (idx == -1) return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
    // k乗
    // 元の数は変更されない
    Matrix pow(ll k) const {
        auto res = I(A.size());
        auto M = *this;
        while (k > 0) {
            if (k & 1) {
                res *= M;
            }
            M *= M;
            k >>= 1;
        }
        return res;
    }
};
int main() {
    ll n, k;
    cin >> n >> k;
    if (n >= 31) {
        vector< int > a(n);
        vector< mint > b(k), s(k);
        mint sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
            b[i] = a[i];
            if (i - 1 >= 0)
                s[i] = s[i - 1] + b[i];
            else
                s[i] = b[i];
        }
        for (int i = n; i < k; i++) {
            b[i] = sum;
            sum += b[i] - b[i - n];
            s[i] = s[i - 1] + b[i];
        }
        cout << b[k - 1] << " " << s[k - 1] << endl;
    } else {
        mint ans = 0;
        vector< int > a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n - 2; i++) {
            ans += mint(a[i]) * (n - 1 - (i + 1));
        }
        //cout << "1:" << ans << endl;
        ans -= a[n - 1];
        //cout << "2:" << ans << endl;
        Matrix< mint > mat(n);
        for (int i = 0; i < n; i++) {
            mat.A[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j + 1) {
                    mat.A[i][j] = 1;
                } else {
                    mat.A[i][j] = 0;
                }
            }
        }
        auto v = mat.pow(k + 1 - n);
        for (int i = 0; i < n; i++) {
            ans += v.A[0][i] * a[n - 1 - i];
        }
        mint ans2 = 0;
        v = mat.pow(k - n);
        for (int i = 0; i < n; i++) {
            ans2 += v.A[0][i] * a[n - 1 - i];
        }
        //cout << "3:" << ans << endl;
        for (ll i = k - n + 2; i <= k; i++) {
            if (i <= n) {
                ans += a[i - 1] * (n-k-1+i);
            }
            v = mat.pow(i - n);
            for (int j = 0; j < n; j++) {
                ans += v.A[0][j] * a[n - 1 - j] * (n-k-1+i);
            }
        }
        cout << ans2 << " " << ans / (n-1) << endl;
    }
    return 0;
}