結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | tottoripaper |
提出日時 | 2015-04-26 23:58:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 44 ms / 5,000 ms |
コード長 | 2,922 bytes |
コンパイル時間 | 543 ms |
コンパイル使用メモリ | 53,512 KB |
実行使用メモリ | 10,824 KB |
最終ジャッジ日時 | 2023-09-18 12:09:48 |
合計ジャッジ時間 | 2,413 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 44 ms
4,380 KB |
testcase_03 | AC | 5 ms
4,376 KB |
testcase_04 | AC | 17 ms
4,376 KB |
testcase_05 | AC | 14 ms
4,380 KB |
testcase_06 | AC | 18 ms
4,376 KB |
testcase_07 | AC | 27 ms
4,380 KB |
testcase_08 | AC | 3 ms
4,376 KB |
testcase_09 | AC | 21 ms
4,380 KB |
testcase_10 | AC | 8 ms
4,376 KB |
testcase_11 | AC | 9 ms
4,376 KB |
testcase_12 | AC | 15 ms
4,376 KB |
testcase_13 | AC | 6 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 33 ms
4,380 KB |
testcase_16 | AC | 29 ms
4,376 KB |
testcase_17 | AC | 8 ms
4,380 KB |
testcase_18 | AC | 30 ms
4,380 KB |
testcase_19 | AC | 43 ms
4,380 KB |
testcase_20 | AC | 11 ms
10,824 KB |
testcase_21 | AC | 12 ms
10,816 KB |
testcase_22 | AC | 11 ms
10,808 KB |
testcase_23 | AC | 3 ms
4,376 KB |
testcase_24 | AC | 7 ms
7,140 KB |
testcase_25 | AC | 7 ms
7,124 KB |
testcase_26 | AC | 7 ms
7,144 KB |
testcase_27 | AC | 7 ms
9,076 KB |
testcase_28 | AC | 3 ms
4,376 KB |
testcase_29 | AC | 10 ms
10,112 KB |
testcase_30 | AC | 44 ms
4,384 KB |
testcase_31 | AC | 1 ms
4,380 KB |
testcase_32 | AC | 13 ms
4,376 KB |
testcase_33 | AC | 19 ms
4,376 KB |
testcase_34 | AC | 16 ms
4,376 KB |
testcase_35 | AC | 12 ms
4,380 KB |
testcase_36 | AC | 31 ms
4,376 KB |
testcase_37 | AC | 3 ms
4,376 KB |
testcase_38 | AC | 36 ms
4,376 KB |
testcase_39 | AC | 14 ms
4,384 KB |
ソースコード
// Wrongri-La Shower #include <cstdio> #include <string> #include <tuple> typedef long long ll; typedef std::tuple<ll,ll> P; struct Matrix{ Matrix(){ for(int i=0;i<=60;i++){ for(int j=0;j<=60;j++){ element[i][j] = 0; } } } ll element[61][61]; }; const ll MOD = 1000000000ll + 7; ll N, K; ll A[10001], B[1000001]; P solve(){ ll sum = 0ll, sum2 = 0ll; for(int i=1;i<=K;i++){ if(i <= N){ B[i] = A[i]; sum = (sum + B[i]) % MOD; }else{ B[i] = sum; sum = (sum + B[i] + (-B[i-N] % MOD + MOD) % MOD) % MOD; } sum2 = (sum2 + B[i]) % MOD; } return std::make_tuple(B[K], sum2); } Matrix multiply(const Matrix &matrix, const Matrix &matrix2, int n){ Matrix mat; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ mat.element[i][j] = 0ll; } } for(int i=1;i<=n;i++){ for(int k=1;k<=n;k++){ for(int j=1;j<=n;j++){ mat.element[i][j] = (mat.element[i][j] + matrix.element[i][k] * matrix2.element[k][j] % MOD) % MOD; } } } return mat; } P solve2(){ if(K <= N){ ll sum = 0ll; for(int i=1;i<=K;i++){ sum = (sum + A[i]) % MOD; } return std::make_tuple(A[K] % MOD, sum); } Matrix matrix, matrix2, matrix3; for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ if(i == 1){ matrix.element[i][j] = 1; }else if(j+1 == i){ matrix.element[i][j] = 1; } } matrix.element[i+N][i] = 1; matrix.element[i+N][i+N] = 1; } for(int i=1;i<=2*N;i++){ matrix2.element[i][i] = 1; } matrix3 = matrix; ll k = K-1; while(k > 0){ if(k & 1){ matrix2 = multiply(matrix2, matrix, 2*N); } k >>= 1; matrix = multiply(matrix, matrix, 2*N); } // for(int i=1;i<=N;i++){ // for(int j=1;j<=N;j++){ // printf("%lld%c", matrix2.element[i][j], ",\n"[j==N]); // } // } // puts(std::string(40, '-').c_str()); ll value = 0ll, sum = 0ll; for(int i=1;i<=N;i++){ value = (value + matrix2.element[N][i] * A[N-i+1] % MOD) % MOD; } matrix2 = multiply(matrix2, matrix3, 2*N); for(int i=1;i<=N;i++){ sum = (sum + matrix2.element[2*N][i] * A[N-i+1] % MOD) % MOD; } // for(int i=1;i<=N;i++){ // res = (res + matrix2.element[1][i] * A[N-i+1] % MOD) % MOD; // } return std::make_tuple(value, sum); } int main(){ scanf("%lld %lld", &N, &K); for(int i=1;i<=N;i++){ scanf("%lld", A+i); } ll x, y; if(K <= 1000000){ std::tie(x, y) = solve(); }else{ std::tie(x, y) = solve2(); } printf("%lld %lld\n", x, y); }