結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | 🍡yurahuna |
提出日時 | 2016-04-08 05:38:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 2,788 bytes |
コンパイル時間 | 2,006 ms |
コンパイル使用メモリ | 178,420 KB |
実行使用メモリ | 11,160 KB |
最終ジャッジ日時 | 2024-10-10 23:54:35 |
合計ジャッジ時間 | 3,227 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i=0;i<(n);i++)#define rep2(i,a,b) for (int i=(a);i<(b);i++)#define rrep(i,n) for (int i=(n)-1;i>=0;i--)#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)#define all(a) (a).begin(),(a).end()typedef long long ll;typedef pair<int, int> P;typedef vector<int> vi;typedef vector<P> vp;typedef vector<ll> vll;typedef vector<ll> Vec;typedef vector<Vec> Mat;const ll mod = 1e9 + 7;Mat mulMatMat(Mat A, Mat B) {int n = A.size();Mat C(n, Vec(n, 0));rep(i, n) {rep(j, n) {rep(k, n) {C[i][j] += A[i][k] * B[k][j];C[i][j] %= mod;}}}return C;}Vec mulMatVec(Mat A, Vec vec) {int n = A.size();Vec res(n, 0);reverse(all(vec)); // 添え字の大きい要素を上に持ってくるためrep(i, n) {rep(j, n) {res[i] += A[i][j] * vec[j];res[i] %= mod;}}return res;}Mat powMat(Mat A, ll p) {int n = A.size();Mat R(n, Vec(n, 0));rep(i, n) R[i][i] = 1; // 単位行列for (; p >= 1; p /= 2) {if (p & 1) {R = mulMatMat(A, R);}A = mulMatMat(A, A);}return R;}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);ll N, K;cin >> N >> K;vll a(N);rep(i, N) cin >> a[i];if (N <= (ll)1e4 && K <= (ll)1e6) {vll f(K);ll t = 0;rep(i, N) {f[i] = a[i];t += f[i];t %= mod;}rep2(i, N, K) {f[i] = t;t = (t + mod - f[i - N]) % mod;t += f[i];t %= mod;}ll s = 0;rep(i, K) {s += f[i];s %= mod;}cout << f[K - 1] << " " << s << endl;} else {// Sを行列累乗で計算Mat A(N + 1, Vec(N + 1, 0));A[0][0] = 2;A[0][N] = -1 + mod;rep2(i, 1, N + 1) A[i][i-1] = 1;// 初期ベクトル s を計算しておくVec f(N + 1, 0);rep(i, N) f[i] = a[i];rep(i, N) f[N] += f[i];Vec s(N + 1, 0);rep(i, N + 1) s[i] = f[i];rep(i, N) s[i + 1] += s[i];A = powMat(A, K - (N + 1));s = mulMatVec(A, s); // s[k], s[k-1], ...cout << (s[0] - s[1] + mod) % mod << " " << s[0] << endl;}}// // Fを直接計算する場合// Mat A(N, Vec(N, 0));// rep(i, N) A[0][i] = 1;// rep2(i, 1, N) A[i][i - 1] = 1;//// auto B = powMat(A, K - N);// auto vec = mulMatVec(B, a);// ll fk = vec[0];// for (auto x : vec) {// cout << x << " ";// }// cout << endl;//// cout << fk << endl;