結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | ctyl_0 |
提出日時 | 2015-10-04 18:26:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 28 ms / 5,000 ms |
コード長 | 3,206 bytes |
コンパイル時間 | 853 ms |
コンパイル使用メモリ | 93,708 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-19 19:34:55 |
合計ジャッジ時間 | 2,213 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <numeric>#include <functional>#include <cmath>#include <queue>#include <stack>#include <set>#include <map>#define repd(i,a,b) for (int i=(a);i<(b);i++)#define rep(i,n) repd(i,0,n)#define mod 1000000007typedef long long ll;using namespace std;int inputValue(){int a;cin >> a;return a;};template <typename T>void output(T a, int precision) {if(precision > 0){cout << setprecision(precision) << a << "\n";}else{cout << a << "\n";}}vector<vector<ll>> multi_mat(vector<vector<ll>> a, vector<vector<ll>> b, ll m){vector<vector<ll>> ret(a.size(), vector<ll>(a.size(), 0));rep(i, a.size()){rep(j, a.size()){rep(k, a.size()){ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % m;}}}return ret;}vector<vector<ll>> pow_mat(vector<vector<ll>> mat, ll pow, ll m){vector<vector<ll>> ret(mat.size(), vector<ll>(mat.size(), 0));rep(i, mat.size()){ret[i][i] = 1;}while (pow > 0) {if (pow & 1) {ret = multi_mat(mat, ret, m);}mat = multi_mat(mat, mat, m);pow >>= 1;}return ret;}int main() {// source codeint N; // 10^4, 30ll K; // 10^6, 10^12cin >> N >> K;vector<int> A(N); // 9for (int i = 0; i < N; i++) {cin >> A[i];}if (N > 30) { // #1 N > 30vector<ll> S(K); // 10^6S[0] = A[0];repd(i, 1, N){S[i] = (A[i] + S[i - 1]) % mod;}if (K >= N) {for (ll i = N; i < K; i++) {if (i == N) {S[i] = (2 * S[i - 1]) % mod;}else{S[i] = (2 * S[i - 1] - S[i - (N + 1)] + mod) % mod;}}}cout << (S[K - 1] - S[K - 2] + mod) % mod << " ";cout << S[K - 1] << endl;// F(K), S(K)}else{ // #2 K largevector<ll> S(N); // 30S[0] = A[0];repd(i, 1, N){S[i] = (A[i] + S[i - 1]) % mod;}if (N >= K) {cout << (S[K - 1] - S[K - 2] + mod) % mod << " ";cout << S[K - 1] << endl;// F(K), S(K)return 0;}// コンパニオン行列の作成vector<vector<ll>> mat(N + 1, vector<ll>(N + 1));rep(i, N + 1){mat[0][i] = 1;}repd(i, 1, N + 1){mat[1][i] = 1;}repd(i, 2, N + 1){mat[i][i - 1] = 1;}vector<vector<ll>> ret = pow_mat(mat, K - N, mod);ll Sk = 0;ll Fk = 0;rep(i, N + 1){if (i == 0) {Sk = (S[N - 1] * ret[0][0]) % mod;continue;}Sk = (Sk + A[N - i] * ret[0][i]) % mod;}repd(i, 1, N + 1){Fk = (Fk + A[N - i] * ret[1][i]) % mod;}cout << Fk << " ";cout << Sk << endl;}return 0;}