結果
問題 | No.3036 Restricted Lucas (Easy) |
ユーザー | kurenai3110 |
提出日時 | 2018-04-02 01:12:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 1,741 ms |
コンパイル使用メモリ | 66,016 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 06:26:06 |
合計ジャッジ時間 | 1,544 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 30 ms
5,376 KB |
testcase_03 | AC | 31 ms
5,376 KB |
testcase_04 | AC | 30 ms
5,376 KB |
testcase_05 | AC | 30 ms
5,376 KB |
testcase_06 | AC | 29 ms
5,376 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; const int zero = false; const int one = true; const int two = one + true; const int three = two + true; const int four = three + true; const int five = four + true; const int six = five + true; const int seven = six + true; const int eight = seven + true; const int nine = eight + true; const int ten = nine + true; ll product(ll a, ll b) { if (b == zero)return zero; ll cnt = one; ll ret = a; while (b >= cnt + cnt) { ret += ret; cnt += cnt; } return ret + product(a, b - cnt); } const int MOD = product(product(product(product(product(product(product(product(ten, ten), ten), ten), ten), ten), ten), ten), ten) + seven; ll mod(ll a, ll b) { while (a >= b) { ll m = b; while (a >= m + m)m += m; a -= m; } return a; } vector<vector<ll>> mul(vector<vector<ll>>&a, vector<vector<ll>>&b, ll p) { vector<vector<ll>>c(a.size(), vector<ll>(b.size())); for (ll i = zero; i<a.size(); i++) { for (ll k = zero; k<b.size(); k++) { for (ll j = zero; j<b[zero].size(); j++) { c[i][j] = mod((c[i][j] + product(a[i][k],b[k][j])), p); } } } return c; } vector<vector<ll>> pow(vector<vector<ll>>&a, ll n, ll p) { vector<vector<ll>>b(a.size(), vector<ll>(a.size())); for (ll i = zero; i<a.size(); i++) { b[i][i] = one; } while (n>zero) { if (n & one) b = mul(a, b, p); a = mul(a, a, p); n >>= one; } return b; } ll fibonacci(ll n, ll p) { vector<vector<ll>>a(two, vector<ll>(two)); a[zero][zero] = one; a[zero][one] = one; a[one][zero] = one; a[one][one] = zero; a = pow(a, n + one, p); return a[one][zero]; } int main() { int T; cin >> T; for (int i = zero; i < T; i++) { int N; cin >> N; cout << mod(fibonacci(N-two, MOD) + fibonacci(N, MOD), MOD) << endl; } return zero; }