結果

問題 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0