結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | codershifth |
提出日時 | 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 |
ソースコード
#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 < 0value_ = (((-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 AOPTbool 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 overloadoperator 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 primeModInt 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 OPTMat 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<jif (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;elseos<<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);elsesolve_matrix(N, K, A);}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new Fibonacchi1();obj->solve();delete obj;return 0;}#endif