結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | mamekin |
提出日時 | 2015-05-24 23:27:13 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 11 ms / 5,000 ms |
コード長 | 2,761 bytes |
コンパイル時間 | 1,069 ms |
コンパイル使用メモリ | 104,932 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-06 08:08:45 |
合計ジャッジ時間 | 1,926 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>using namespace std;const int MOD = 1000000007;// 行列の積template <class T>vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y){int a = x.size();int b = x[0].size();int c = y[0].size();vector<vector<T> > z(a, vector<T>(c, 0));for(int i=0; i<a; ++i){for(int j=0; j<c; ++j){for(int k=0; k<b; ++k){z[i][j] += x[i][k] * y[k][j];z[i][j] %= MOD;}}}return z;}// 行列の累乗template <class T>vector<vector<T> > matrixPower(const vector<vector<T> >& x, long long k){int n = x.size();vector<vector<T> > y(n, vector<T>(n, 0));for(int i=0; i<n; ++i)y[i][i] = 1; // 積の単位元vector<vector<T> > z = x;while(k > 0){if(k & 1)y = matrixProduct(y, z);z = matrixProduct(z, z);k >>= 1;}return y;}pair<long long, long long> solve1(const vector<int>& a, long long k){int n = a.size();queue<int> q;int sum = 0;for(int i=0; i<n; ++i){sum += a[i];sum %= MOD;q.push(a[i]);}pair<long long, long long> ans(-1, sum);for(int i=n; i<k; ++i){ans.first = sum;ans.second += sum;ans.second %= MOD;q.push(sum);sum += sum;sum -= q.front();sum = (sum % MOD + MOD) % MOD;q.pop();}return ans;}pair<long long, long long> solve2(const vector<int>& a, long long k){int n = a.size();vector<vector<long long> > mat(n+1, vector<long long>(n+1, 0));for(int i=0; i<n-1; ++i)mat[i][i+1] = 1;for(int i=0; i<n; ++i)mat[n-1][i] = 1;mat[n][0] = mat[n][n] = 1;mat = matrixPower(mat, k - 1);pair<long long, long long> ans(0, 0);for(int i=0; i<n; ++i){ans.first += mat[0][i] * a[i];ans.first %= MOD;ans.second += mat[n][i] * a[i];ans.second %= MOD;}ans.second += ans.first;ans.second %= MOD;return ans;}int main(){int n;long long k;cin >> n >> k;vector<int> a(n);for(int i=0; i<n; ++i)cin >> a[i];pair<long long, long long> ans;if(n > 30)ans = solve1(a, k);elseans = solve2(a, k);cout << ans.first << ' ' << ans.second << endl;return 0;}