結果
問題 | No.3036 Restricted Lucas (Easy) |
ユーザー | Pachicobue |
提出日時 | 2018-04-02 02:58:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 2,315 bytes |
コンパイル時間 | 860 ms |
コンパイル使用メモリ | 70,784 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 06:28:59 |
合計ジャッジ時間 | 1,393 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 4 ms
5,376 KB |
testcase_02 | AC | 37 ms
5,376 KB |
testcase_03 | AC | 38 ms
5,376 KB |
testcase_04 | AC | 36 ms
5,376 KB |
testcase_05 | AC | 37 ms
5,376 KB |
testcase_06 | AC | 37 ms
5,376 KB |
ソースコード
#include <iostream> #include <array> using namespace std; using ll = long long; constexpr ll zero = static_cast<ll>(NULL); constexpr ll one = sizeof(char); constexpr ll two = sizeof(short); constexpr ll four = sizeof(int); constexpr ll eight = sizeof(long); ll MOD; inline ll add(ll a, ll b) { while (b != zero) { ll c = (a & b) << one; a ^= b; b = c; } return a; } inline ll sub(const ll a, const ll b) { return add(a, add(~b, one)); } inline ll mul(const ll a, const ll b) { ll ans = zero; static const ll sixteen = add(eight, eight); static const ll thirtytwo = add(sixteen, sixteen); static const ll sixtyfour = add(thirtytwo, thirtytwo); for (ll i = zero; i < sixtyfour; i = add(i, one)) { if (a & (one << i)) { ans = add(ans, b << i); } } return ans; } inline ll mod(ll n, ll d = MOD) { ll m = one, q = zero; while (d <= n) { d <<= one; m <<= one; } while (one < m) { d >>= one; m >>= one; if (n >= d) { n = sub(n, d); q |= m; } } return n; } using Mat = array<array<ll, two>, two>; Mat mul(const Mat& a, const Mat& b) { Mat ans{{{zero, zero}, {zero, zero}}}; for (ll i = zero; i < two; i = add(i, one)) { for (ll j = zero; j < two; j = add(j, one)) { for (ll k = zero; k < two; k = add(k, one)) { ans[i][j] = mod(add(ans[i][j], mod(mul(a[i][k], b[k][j])))); } } } return ans; } Mat power(const Mat& m, const ll n) { if (n == zero) { return Mat{{{one, zero}, {zero, one}}}; } if (mod(n, two) == one) { return mul(power(m, sub(n, one)), m); } else { const auto pp = power(m, n >> one); return mul(pp, pp); } } int main() { MOD = one; const ll ten = add(two, eight); for (ll i = zero; i <= eight; i = add(i, one)) { MOD = mul(MOD, ten); } MOD = add(MOD, eight); MOD = sub(MOD, one); ll T; cin >> T; const Mat mat{{{one, one}, {one, zero}}}; for (ll i = zero; i < T; i = add(i, one)) { ll N; cin >> N; const auto ans = power(mat, N); cout << mod(add(ans[one][zero], mul(two, ans[one][one]))) << endl; } return zero; }