結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | no15_renne |
提出日時 | 2015-04-26 23:32:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 2,611 bytes |
コンパイル時間 | 984 ms |
コンパイル使用メモリ | 80,884 KB |
実行使用メモリ | 11,048 KB |
最終ジャッジ日時 | 2024-07-05 02:27:50 |
合計ジャッジ時間 | 3,015 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <vector>#include <algorithm>#include <set>#include <queue>#include <map>#include <climits>using namespace std;#define REP(i,n) for(int i=0; i<(int)(n); i++)#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)#define ALL(c) (c).begin(), (c).end()typedef long long int ll;typedef pair<int, int> pii;typedef pair<int, pair<int, int> > pipii;typedef vector<int> vi;const int INF = 1e9;const ll MOD = 1e9+7;typedef ll number;typedef vector<number> Array;typedef vector<Array> Matrix;Matrix mul(const Matrix &a, const Matrix &b){Matrix res(a.size(), Array(b[0].size()));REP(i, a.size()){REP(j, b[0].size()){REP(k, a[0].size()){(res[i][j] += a[i][k] * b[k][j]) %= MOD;}}}return res;}Matrix powMat(const Matrix &a, ll b){if(!b){Matrix res(a.size(), Array(a.size()));REP(i, a.size()) res[i][i] = 1;return res;}Matrix res = powMat(mul(a, a), b / 2);if(b&1) res = mul(res, a);return res;}int main(void){int n;ll k;cin >> n >> k;if(k <= 1000000){vector<ll> a(k, 0LL);REP(i, n) cin >> a[i];REP(i, n) (a[n] += a[i]) %= MOD;REP(i, k){if(i < n + 1 || a[i]) continue;a[i] = (a[i-1] + a[i-1] - a[i-n-1] + MOD) % MOD;}cout << a[k-1] << " ";ll ans = 0LL;REP(i, k){(ans += a[i]) %= MOD;}cout << ans << endl;}else{Matrix x(n*2, Array(1, 0LL)), b(n*2, Array(1, 0LL));Matrix A(n*2, Array(n*2, 0LL));REP(i, n){cin >> x[n*2 - i*2-2][0];x[n*2 - i*2 - 1][0] = x[n*2 - i*2 - 2][0];}REP(i, n){if(!i) continue;x[n*2 - i*2 - 1][0] += x[n*2 - (i-1)*2 - 1][0];}REP(i, n){A[0][i*2] = 1LL;A[1][i*2] = 1LL;}A[1][1] = 1LL;REP(i, n*2-2){A[i+2][i] = 1LL;}/*REP(i, n*2){cout << x[i][0] << ":";}cout << endl;REP(i, n*2){REP(j, n*2){cout << A[i][j] << ":";}cout << endl;}cout << endl;*/b = mul(powMat(A, k-n), x);cout << b[0][0] << " " << b[1][0] << endl;}return 0;}