結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | rantd |
提出日時 | 2015-04-30 18:59:51 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,279 bytes |
コンパイル時間 | 1,504 ms |
コンパイル使用メモリ | 171,916 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-07-05 17:12:49 |
合計ジャッジ時間 | 2,756 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 9 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 5 ms
5,376 KB |
testcase_10 | AC | 3 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 7 ms
5,376 KB |
testcase_16 | AC | 7 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 7 ms
5,376 KB |
testcase_19 | AC | 9 ms
5,376 KB |
testcase_20 | AC | 16 ms
11,136 KB |
testcase_21 | AC | 17 ms
11,136 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 8 ms
6,656 KB |
testcase_27 | AC | 9 ms
7,552 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 9 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 3 ms
5,376 KB |
testcase_33 | AC | 5 ms
5,376 KB |
testcase_34 | AC | 4 ms
5,376 KB |
testcase_35 | AC | 3 ms
5,376 KB |
testcase_36 | AC | 7 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 8 ms
5,376 KB |
testcase_39 | AC | 4 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define repu(i, begin, end) for (__typeof(begin) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define repe(i, begin, end) for (__typeof(begin) i = (begin); i != (end) + 1 - 2 * ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define mem(a, x) memset(a, x, sizeof(a)) #define all(a) a.begin(), a.end() #define count_bits(x) __builtin_popcount(x) #define count_bitsll(x) __builtin_popcountll(x) #define least_bits(x) __builtin_ffs(x) #define least_bitsll(x) __builtin_ffsll(x) #define most_bits(x) 32 - __builtin_clz(x) #define most_bitsll(x) 64 - __builtin_clz(x) vector<string> split(const string &s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(x); return v; } #define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); } void err(vector<string>::iterator it) {} template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n'; err(++it, args...); } typedef long long ll; const int MOD = 1000000007; template<class T> inline T tmin(T a, T b) {return (a < b) ? a : b;} template<class T> inline T tmax(T a, T b) {return (a > b) ? a : b;} template<class T> inline void amax(T &a, T b) {if (b > a) a = b;} template<class T> inline void amin(T &a, T b) {if (b < a) a = b;} template<class T> inline T tabs(T a) {return (a > 0) ? a : -a;} template<class T> T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;} const int N = 1000005; int n, a[N]; ll k; typedef vector<ll> vl; typedef vector<vl> Mat; void unit(Mat &data) { int sz = data.size(); repu(i, 0, sz) data[i][i] = 1; } Mat mul(Mat x, Mat y) { int sz = x.size(); Mat ans(sz, vl(sz, 0)); repu(i, 0, sz) repu(j, 0, sz) repu(k, 0, sz) { ans[i][j] = (ans[i][j] + x[i][k] * y[k][j]) % MOD; } return ans; } Mat pow(Mat x, ll n) { int sz = x.size(); Mat ans(sz, vl(sz, 0)); unit(ans); while (n) { if (n & 1) ans = mul(ans, x); x = mul(x, x); n >>= 1; } return ans; } void solve_small() { vector<ll> f(k); ll s = 0, tot = 0; repu(i, 0, n) { f[i] = a[i]; tot += a[i]; } s = tot; repu(i, n, k) { f[i] = tot % MOD; tot = (tot + f[i] - f[i - n]) % MOD; s = (s + f[i]) % MOD; } if (f[k - 1] < 0) f[k - 1] += MOD; printf("%lld %lld\n", f[k - 1], s); } void solve_large() { Mat base(n + 1, vl(n + 1, 0)); repu(i, 0, n) base[0][i] = 1; repu(i, 1, n) base[i][i - 1] = 1; repu(i, 0, n + 1) base[n][i] = 1; ll tot = 0; repu(i, 0, n) tot += a[i]; Mat ret = pow(base, k - n); ll fk = 0, s = 0; repu(i, 0, n) { fk += ret[0][i] * a[n - 1 - i]; s += ret[n][i] * a[n - 1 - i]; } fk += ret[0][n] * tot; fk %= MOD; s += ret[n][n] * tot; s %= MOD; printf("%lld %lld\n", fk, s); } int main(int argc, char *argv[]) { ios_base::sync_with_stdio(false); cin >> n >> k; repu(i, 0, n) cin >> a[i]; if (n <= 10000 && k < N) solve_small(); else solve_large(); return 0; }