結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | NyaanNyaan |
提出日時 | 2019-06-11 17:16:12 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 18 ms / 5,000 ms |
コード長 | 11,446 bytes |
コンパイル時間 | 1,582 ms |
コンパイル使用メモリ | 115,268 KB |
実行使用メモリ | 18,996 KB |
最終ジャッジ日時 | 2024-10-06 10:03:57 |
合計ジャッジ時間 | 2,506 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 17 ms
6,820 KB |
testcase_03 | AC | 3 ms
6,820 KB |
testcase_04 | AC | 7 ms
6,820 KB |
testcase_05 | AC | 6 ms
6,816 KB |
testcase_06 | AC | 8 ms
6,816 KB |
testcase_07 | AC | 11 ms
6,820 KB |
testcase_08 | AC | 3 ms
6,816 KB |
testcase_09 | AC | 9 ms
6,820 KB |
testcase_10 | AC | 4 ms
6,816 KB |
testcase_11 | AC | 5 ms
6,816 KB |
testcase_12 | AC | 7 ms
6,816 KB |
testcase_13 | AC | 3 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 14 ms
6,816 KB |
testcase_16 | AC | 11 ms
6,816 KB |
testcase_17 | AC | 4 ms
6,820 KB |
testcase_18 | AC | 12 ms
6,820 KB |
testcase_19 | AC | 16 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,816 KB |
testcase_21 | AC | 18 ms
18,996 KB |
testcase_22 | AC | 2 ms
6,820 KB |
testcase_23 | AC | 3 ms
6,820 KB |
testcase_24 | AC | 11 ms
10,664 KB |
testcase_25 | AC | 9 ms
10,024 KB |
testcase_26 | AC | 10 ms
9,624 KB |
testcase_27 | AC | 10 ms
11,700 KB |
testcase_28 | AC | 4 ms
6,816 KB |
testcase_29 | AC | 16 ms
17,476 KB |
testcase_30 | AC | 16 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,816 KB |
testcase_32 | AC | 7 ms
6,820 KB |
testcase_33 | AC | 8 ms
6,816 KB |
testcase_34 | AC | 7 ms
6,820 KB |
testcase_35 | AC | 6 ms
6,816 KB |
testcase_36 | AC | 13 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,816 KB |
testcase_38 | AC | 15 ms
6,820 KB |
testcase_39 | AC | 7 ms
6,816 KB |
ソースコード
#pragma GCC optimize("O2") #include <algorithm> #include <cassert> #include <cmath> #include <cstdarg> #include <cstdio> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <iterator> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> #define whlie while #define mp make_pair #define pb emplace_back #define fi first #define se second #define inf 1001001001 #define infLL ( (1LL << 61)) #define FOR(i,a,b) for(int (i)=((int)a); (i)<((int)b); (i)++) // [a,b) #define rep(i,N) FOR((i), 0, ((int)N)) // [0,N) #define FORR(i,a,b) for(int (i)=((int)b) - 1; (i)>=((int)a); (i)--) #define repr(i,N) FORR((i), 0, ((int)N)) #define all(v) (v).begin(),(v).end() #define sz(v) ((int)(v).size()) #define vrep(v,it) for(auto it=v.begin();it!=v.end();it++) #define vrepr(v,it) for(auto it=v.rbegin();it!=v.rend();it++) #define inx(t,...) t __VA_ARGS__; in(__VA_ARGS__) #define ini(...) int __VA_ARGS__; in(__VA_ARGS__) #define inl(...) ll __VA_ARGS__; in(__VA_ARGS__) #define inc(...) char __VA_ARGS__; in(__VA_ARGS__) #define ins(...) string __VA_ARGS__; in(__VA_ARGS__) #define ind(...) double __VA_ARGS__; in(__VA_ARGS__) #define inpii(...) pii __VA_ARGS__; in(__VA_ARGS__) #define invi(v,...) vi v; in(v,##__VA_ARGS__) #define invl(v,...) vl v; in(v,##__VA_ARGS__) #define mem(ar,val) memset((ar), (val), sizeof(ar) ) #define mem0(ar) memset((ar), 0, sizeof(ar) ) #define mem1(ar) memset((ar), -1, sizeof(ar) ) #ifdef LOCAL #define dbg(...) fprintf(stderr, __VA_ARGS__) #define trc(...) do { cout << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0) #define stopif(val) assert( !(val) ) #define vdbg(v,...) do { cout << #v << " = "; vector_debug(v , ##__VA_ARGS__);} while(0) #else #define dbg(...) 1 #define trc(...) 1 #define stopif(...) 1 #define vdbg(...) 1 #endif using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<string> vs; typedef vector<pii> vpii; typedef vector< vector<int> > vvi; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } iosetup; int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} int lcm(int a, int b){return (a / gcd(a,b)) * b;} ll lcm(ll a, ll b){return (a / gcd(a,b)) * b;} inline ll pow(int a, int b){ll ans = 1; rep(i,b) ans *= a; return ans;} inline ll pow(ll a, ll b){ll ans = 1; rep(i,b) ans*= a; return ans;} inline ll pow(int a, ll b){ll ans = 1; rep(i,b) ans *= a; return ans;} inline ll pow(ll a, int b){ll ans = 1; rep(i,b) ans*= a; return ans;} template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template<typename C> inline void _cin(C &c){cin >> c;} template<typename T,typename U> inline void _cin(pair<T,U> &p){cin >> p.fi; cin >> p.se;} template<typename C> inline void _cout(const C &c){cout << c;} template<typename T,typename U> inline void _cout(const pair<T,U> &p){cout << p.fi << ' ' << p.se;} void in(){} template <typename T,class... U> void in(T &t,U &...u){ _cin(t); in(u...);} void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ' '; out(u...);} template<typename C> inline void in(vector<C> &v,int N=-1){if(sz(v) != 0){int M=(N == -1) ? sz(v) : N; rep(i,M) _cin(v[i]);}else{C c;rep(i,N) v.pb((_cin(c),c));}} template<typename C> inline void in(C v[],int N){rep(i,N) _cin(v[i]);} template<typename C> inline void out(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<"\n";} template<typename C> inline void out(C v[],int N){rep(i,N) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<"\n";} template<typename C> inline void vector_debug(const vector<C> &v,int N=-1){cout << "{"; int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?", ":"" ); _cout(v[i]);} cout<<"}"<<endl;} template<typename C> inline void vector_debug(C v[], int N){cout << "{"; rep(i,N) {cout<<((i)?", ":""); _cout(*(v+i));} cout<<"}"<<endl;} void dbg_out(){cout << endl;} template <typename T,class... U> void dbg_out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C,class... U> void dbg_out(const vector<C> &v,U ...u){vector_debug(v); if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C,class... U> void dbg_out(const vector<vector<C>> &v,U ...u){cout << "{ "; rep(i,sz(v)) {if(i)cout<<", "; vector_debug(v[i]);} cout << " }"; if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C> inline C vmax(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amax(n,v[i]); return n;} template<typename C> inline C vmax(C v[], int N){C n=v[0]; rep( i , N ) amax(n,v[i]); return n;} template<typename C> inline C vmin(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amin(n,v[i]); return n;} template<typename C> inline C vmin(C v[], int N){C n=v[0]; rep( i , N ) amin(n,v[i]); return n;} template<typename C> inline C vsum(const vector<C> &v){C n=0; rep(i,sz(v)) n+=v[i]; return n;} template<typename C> inline C vsum(C v[], int N){C n=0; rep( i , N ) n+=v[i]; return n;} //////////// /// main /// //////////// template< int mod > struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t 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; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); } }; template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector< T > &operator[](int k) const { return (A.at(k)); } inline 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 ll &m){ for(int i=0; i < height(); i++) for(int j=0; j < width(); j++){ (*this)[i][j] += m; (*this)[i][j] %= m; } 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()); vector< vector< T > > C(n, 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]) % (T)1000000007; A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(height()); while(k > 0) { if(k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator%(const T &m) const{ return (Matrix(*this) %= m); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } friend ostream &operator<<(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); } }; template<typename T> Matrix<T> Mpow(Matrix<T> A, ll N){ if(N == 0){ return A.I(A.height()); } if(N == 1) return A; if(N % 2 == 1) return (Mpow(A, N - 1) * A) % (T)1000000007; Matrix<T> half = Mpow(A , N / 2); return (half * half) % (T)1000000007; } int main(){ constexpr ll mod = 1000000007; inl(N); inl(K); vl A(N + 1); FOR(i, 1, N + 1) in(A[i]); if(K <= N || N > 30){ vl F(K + 10,0),S(K + 10,0); FOR(i,1,N + 1){ F[i] = A[i]; S[i] = S[i - 1] + A[i]; } if( K <= N ) {out(F[K],S[K]); return 0;}; FOR( i , N + 1, K + 1 ){ F[i] = ( S[i - 1] - S[i - N - 1] + mod ) % mod; S[i] = (S[i - 1] + F[i]) % mod; } out(F[K],S[K]); return 0; } Matrix<ll> FM(N); rep(i,N) FM[0][i] = 1; rep(i,N-1) FM[i+1][i] = 1; //cout << FM; Matrix<ll> F(N,1); rep(i,N) F[i][0] = A[N - i]; Matrix<ll> SM(N + 1); SM[0][0] = 2; SM[0][N] = -1; rep(i,N) SM[i+1][i] = 1; Matrix<ll> S(N + 1, 1); FOR(i,1,N + 1){ S[N - i][0] = S[N - i + 1][0] + A[i]; } Matrix<ll> ans = Mpow(FM , K - N) * F; //cout << ans; Matrix<ll> ans2 = Mpow(SM, K - N) * S; out(ans[0][0] , ans2[0][0]); }