結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー |
|
提出日時 | 2015-04-27 12:58:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 2,021 bytes |
コンパイル時間 | 1,515 ms |
コンパイル使用メモリ | 172,372 KB |
実行使用メモリ | 9,444 KB |
最終ジャッジ日時 | 2024-07-05 04:51:33 |
合計ジャッジ時間 | 3,045 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:67:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 67 | scanf("%d%lld", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:70:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%d", &x); | ~~~~~^~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long i64; int mod = 1e9 + 7; pair<int, int> solve1(int n, int k, vector<int> a) { int y = 0; for(int i=0; i<n; i++) { y = (y + a[i]) % mod; } int z = y; for(int i=n; i<k; i++) { a.push_back(z); y = (y + z) % mod; z = ((z + z) % mod - a[i-n] + mod) % mod; } return make_pair(a.back(), y); } vector<vector<i64>> matmul(vector<vector<i64>> a, vector<vector<i64>> b) { vector<vector<i64>> res(a.size(), vector<i64>(b[0].size())); for(int i=0; i<a.size(); i++) { for(int k=0; k<b.size(); k++) { for(int j=0; j<b[0].size(); j++) { res[i][j] = (res[i][j] + a[i][k] * b[k][j] + mod) % mod; } } } return res; } vector<vector<i64>> matpow(vector<vector<i64>> a, i64 n) { vector<vector<i64>> res(a.size(), vector<i64>(a.size())); for(int i=0; i<a.size(); i++) { for(int j=0; j<a.size(); j++) { res[i][j] = i==j?1:0; } } while(n > 0) { if(n & 1) { res = matmul(res, a); } a = matmul(a, a); n >>= 1; } return res; } pair<int, int> solve2(int n, i64 k, vector<int> a) { vector<vector<i64>> s(n+1, vector<i64>(1)); s[n][0] = 0; s[n-1][0] = a[0]; for(int i=1; i<n; i++) { s[n-1-i][0] = s[n-i][0] + a[i]; } vector<vector<i64>> mat(n+1, vector<i64>(n+1)); mat[0][0] = 2; for(int i=0; i<n; i++) { mat[i+1][i] = 1; } mat[0][n] = -1; vector<vector<i64>> powered = matpow(mat, k-n); vector<vector<i64>> res = matmul(powered, s); i64 x = res[0][0], y = res[1][0]; return make_pair((x-y+mod)%mod, x); } int main(void) { int n; i64 k; vector<int> a; scanf("%d%lld", &n, &k); for(int i=0; i<n; i++) { int x; scanf("%d", &x); a.push_back(x); } pair<int, int> res = k<=1e6 ? solve1(n, (int)k, a) : solve2(n, k, a); printf("%d %d\n", res.first, res.second); return 0; }