結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー codershifthcodershifth
提出日時 2015-07-05 11:30:00
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 44 ms / 5,000 ms
コード長 11,058 bytes
コンパイル時間 897 ms
コンパイル使用メモリ 103,180 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-07 23:03:32
合計ジャッジ時間 2,702 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <limits>
#include <tuple>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

class ModInt {
    long long value_;

public:
    static long long Mod;
    static void set_mod(long long mod) { Mod= mod; }
    static long long  get_mod(void) { return Mod; }

    ModInt() : value_(0) {}
    ModInt(long long val) {
            if (val >= Mod)
                value_ = val % Mod;
            else if (val >= 0)
                value_ = val;
            else // val < 0
                value_ = (((-val)/Mod+1)*Mod+val) % Mod;
            assert(value_ < Mod);
    }
    ~ModInt() {}
#define OPT(OP)                                           \
    ModInt operator OP (const ModInt &other) const {      \
            return ModInt(value_ OP other.value_);        \
    }                                                     \
    ModInt operator OP (int other) const {                \
            return ModInt(value_ OP other);               \
    }                                                     \
    friend ModInt operator OP (int a, const ModInt &b) {                \
            return ModInt(a) OP b;                                      \
    }
    OPT(+)
    OPT(-)
    OPT(*)
#undef OPT
#define AOPT(EOP, OP)                 \
    ModInt &operator EOP(const ModInt &other) {   \
            return (*this = (*this OP other));    \
    }
    AOPT(+=, +)
    AOPT(*=, *)
    AOPT(-=, -)
#undef AOPT
    bool operator==(const ModInt &other) const {
            return (value_ == other.value_);
    }
    bool operator!=(const ModInt &other) const {
            return !(*this == other);
    }
    ModInt &operator=(const ModInt &other) {
            value_ = other.value_;
            return *this;
    }
    // cast overload
    operator int() const { return value_; }
    operator long long() const { return value_; }

    static long long pow(long long a, int k) {
            long long  b = 1;
            while (k > 0)
            {
                if (k & 1)
                    b = (b*a)%Mod;
                a = (a*a)%Mod;
                k >>= 1;
            }
            return b;
    }
    // call when Mod is prime
    ModInt inv() {
            return ModInt::pow(value_, Mod-2);
    }
    long long value() const { return value_; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& m) {
            os<<m.value_;
            return os;
    }
};

long long ModInt::Mod = (long long)(1E+9)+7;

template<typename T>
class Mat : public std::vector<std::vector<T>> {
    typedef std::vector<T> vecT;
    typedef std::vector<vecT> vvT;

#undef foreach
#define foreach(X, Y)                           \
    for (int (Y) = 0; (Y) < nrow(); ++(Y))     \
        for (int (X) = 0; (X) < ncol(); ++(X))

public:
    int nrow() const { return vvT::size(); }
    int ncol() const { return vvT::operator[](0).size(); }
    Mat() {}
    ~Mat() {}
    Mat(int n, int m) : vvT(n, vecT(m)) {}
    Mat(int n, int m, T v) : vvT(n, vecT(m, v)) {}
    template <typename S>
    Mat(const std::vector<std::vector<S>> &m) : vvT(m.size(), vecT(m[0].size())) {
        auto &self = *this;
        foreach(x, y)
            self[y][x] = m[y][x];
    }
    template <typename S>
    Mat(const std::vector<S> &vec) : vvT(vec.size(), vecT(1)) {
        auto &self = *this;
        foreach(x, y)
            self[y][x] = vec[y];
    }
    template <typename S>
        Mat(const Mat<S> &other) : Mat(other.nrow(), other.ncol()) {
        auto &self = *this;
        foreach(x, y)
            self[y][x] = other[y][x];
    }
    Mat operate(const Mat &other, const  std::function<T(T,T)> &op) const {
        Mat m(nrow(), ncol());
        const auto &self = *this;
        foreach(x, y)
            m[y][x] = op(self[y][x], other[y][x]);
        return std::move(m);
    }
    Mat operate(const T &d, const std::function<T(T,T)> &op) const {
        Mat m(nrow(), ncol());
        const auto &self = *this;
        foreach(x, y)
            m[y][x] = op(self[y][x], d);
        return std::move(m);
    }
    std::vector<T> col(int k) const {
        assert(0<=k && k<ncol());
        vecT vec(nrow());
        const auto &self = *this;
        for (int i = 0; i < nrow(); ++i)
            vec[i] = self[i][k];
        return std::move(vec);
    }
    std::vector<T> row(int k) const {
        assert(0<=k && k<nrow());
        const auto &self = *this;
        return self[k];
    }
#define OPT(OP) [](const T &a, const T &b)->T { return a OP b; }
    Mat operator+(const Mat &other) const { return operate(other, OPT(+)); }
    Mat operator-(const Mat &other) const { return operate(other, OPT(-)); }
    Mat operator*(const std::vector<T> &vec) const {
        Mat<T> b(vec);
        return operator*(b);
    }
    Mat operator*(const Mat &other) const {
        assert(ncol() == other.nrow());
        Mat m(nrow(), other.ncol());
        const auto &self = *this;
        for (int i = 0; i < nrow(); ++i)
            for (int j = 0; j < other.nrow(); ++j)
                for (int k = 0; k < (int)other[0].size(); ++k)
                    m[i][k] = (m[i][k]+self[i][j]*other[j][k]);
        return std::move(m);
    }
    bool operator==(const Mat &other) const {
        if (ncol() != other.ncol() || nrow() != other.nrow())
            return false;
        const auto &self = *this;
        foreach(x, y) if (self[y][x] != other[y][x])
            return false;
        return true;
    }
    bool operator!=(const Mat &other) const {
        return !(*this == other);
    }
    Mat &operator=(const Mat &other) {
        Mat(other.nrow(), other.ncol());
        auto &self = *this;
        foreach(x, y)
            self[y][x] = other[y][x];
        return self;
    }
    Mat operator*(const T &s) const { return operate(s, OPT(*)); }
    Mat operator/(const T &s) const { return operate(s, OPT(/)); }
    Mat operator+(const T &s) const { return operate(s, OPT(+)); }
    Mat operator-(const T &s) const { return operate(s, OPT(-)); }
    Mat operator%(const T &s) const { return operate(s, OPT(%)); }
#undef OPT
    Mat assign(int row, int col, const Mat &other) {
        auto &self = *this;
        for (int iy = 0; iy < std::min(std::max(nrow()-row, 0), other.nrow()); ++iy)
            for (int ix = 0; ix < std::min(std::max(ncol()-col, 0), other.ncol()); ++ix)
                self[iy+row][ix+col] = other[iy][ix];
        return *this;
    }
    bool is_square() const { return (nrow() == ncol()); }
    double det() const {
        assert(is_square());
        int n = nrow();
        std::vector<int> index(n);
        double res=0;

        for (int i = 0; i < n; ++i)
            index[i]=i;
        do{
            double acc=1.0;
            int    sgn = 1;
            for (int i = 0; i < n; ++i)
                for (int j = i+1; j < n; ++j) // i<j
                    if (index[j]<index[i])    // 逆転
                        sgn *= -1;
            for (int i = 0; i < n; ++i)
                acc *= vvT::operator[](i)[index[i]];
            res += sgn*acc;
        } while (next_permutation(index.begin(), index.end()));
        return res;
    }
#define AOPT(EOP, OP)                 \
    Mat &operator EOP(const T &s) {   \
        *this = (*this OP s);         \
        return *this;                 \
    }
    AOPT(+=, +)
    AOPT(/=, /)
    AOPT(*=, *)
    AOPT(-=, -)
#undef AOPT
    // O(log(k)*nrow(A)^3)
    Mat pow(long long k) {
        Mat a(*this);
        Mat b = one(nrow(), ncol());
        while (k > 0)
        {
            if (k & 1)
                b = b*a;
            a = a*a;
            k >>= 1;
        }
        return std::move(b);
    }
    /* 出力用の<<演算子定義 */
    friend std::ostream& operator<<(std::ostream& os, const Mat& mat) {
        for (int y = 0; y < mat.nrow(); ++y)
        for (int x = 0; x < mat.ncol(); ++x)
        {
            if (x == mat.ncol()-1)
                os<<mat[y][x]<<std::endl;
            else
                os<<mat[y][x]<<" ";
        }
        os<<std::endl;
        return os;
    }
    //
    // class method
    //
    static Mat zero(int n, int m) {
        return Mat(n, m, 0);
    }
    static Mat one(int n, int m) {
        Mat mat(n, m);
        for (int i = 0; i < std::min(n, m); ++i)
            mat[i][i] = 1.0;
        return std::move(mat);
    }
#undef foreach
};

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

const int MOD = (int)1E+9+7;
class Fibonacchi1 {
public:
    // O(max(K,N))
    void solve_dp(int N, ll K, const vector<int> &A) {
            vector<ModInt> S(K+1, 0); // Test Case 3(K_=987654321012) で MLE
            //
            // S(k) = ∑F(i) (1<=i<=k)
            // S(k+1) = F(k+1) + S(k)
            // F(k+1) = F(k)+F(k-1)+...+F(k-N+1) = S(k)-S(k-N)
            // S(k+1) = 2*S(k) - S(k-N)
            //
            // O(k)
            //
            S[1] = A[0];
            FOR(i, 1, N+1)
                S[i] = S[i-1] + A[i-1];

            FOR(k, N, K)
                S[k+1] = 2*S[k] - S[k-N];
            cout<<S[K]-S[K-1]<<" "<<S[K]<<endl;
    }
    // O(N^3*log(K))
    void solve_matrix(int N, ll K, const vector<int> &A) {
            ModInt::set_mod(MOD);
            // S(k+1) = 2*S(k) - S(k-N)
            //
            // |S(k+1)  |    |2 0 0 ... 0 -1 |   |S(k)  |
            // |S(k)    |    |1 0 0 ... 0 0  |   |S(k-1)|
            // |S(k-1)  |  = |0 1 0 ... 0 0  | * |S(k-2)|
            // | :      |    |      :        |   | :    |
            // |S(k-N+1)|    |0 0 0 ... 1 0  |   |S(k-N)|
            //
            //    X(k+1)   = B * X(k)
            //    X(k)     = B * X(k-1) = A^2 * X(k-2) = ...
            //             = B^(k-N) * X(N)
            //
            int n = N+1;
            Mat<ModInt> B(n,n,0);
            Mat<ModInt> X0(n,1,0);
            X0[1][0] = A[0];
            FOR(i, 1, n)
                X0[i][0] = X0[i-1][0] + A[i-1];
            reverse(RANGE(X0));

            B[0][0] = 2;
            B[0][n-1] = -1;
            FOR(i, 1, n)
                B[i][i-1] = 1;
            Mat<ModInt> X = B.pow(K-N)*X0;
            cout<<X[0][0]-X[1][0]<<" "<<X[0][0]<<endl;
    }
    void solve(void) {
            int N;
            ll  K;
            cin>>N>>K;
            vector<int> A(N);
            REP(i, N)
                cin>>A[i];
            if (N > 30)
                solve_dp(N, K, A);
            else
                solve_matrix(N, K, A);
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new Fibonacchi1();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0