結果
問題 | No.8037 Restricted Lucas (Hard) |
ユーザー | みしあ |
提出日時 | 2021-10-22 12:23:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,947 bytes |
コンパイル時間 | 697 ms |
コンパイル使用メモリ | 75,540 KB |
実行使用メモリ | 16,952 KB |
最終ジャッジ日時 | 2024-09-22 14:12:34 |
合計ジャッジ時間 | 7,236 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
ソースコード
#include <iostream> #include <utility> #include <vector> #include <numeric> using namespace std; using ll = long long; const ll t = true, f = false, tt = t << t; ll ad(ll a, ll b){ vector<ll> tmp{a}; return accumulate(tmp.begin(), tmp.end(), b); } ll mn(ll a, ll b){ return ad(a, ad(~b, t)); } template<class... Args> ll Num(Args... args){ ll ret = f; for(auto v : initializer_list<ll>{args...}){ ret <<= t; ret |= v; } return ret; } const ll mod = Num(t,t,t,f,t,t,t,f,f,t,t,f,t,f,t,t,f,f,t,f,t,f,f,f,f,f,f,t,t,t); ll md(ll x){ if(x >= mod){ x = mn(x, mod); } return x; } ll mm(ll a, ll b){ ll ret = f; if(a>b){ swap(a, b); } while(a){ if(a&t){ ret = ad(ret, b); ret = md(ret); } b <<= t; a >>= t; b = md(b); } return ret; } ll pp(ll a, ll b){ ll x = ad(a, b); return md(x); } struct Mat{ ll ul, ur, dl, dr; Mat(){ ul = ur = dl = dr = f; } Mat(ll _ul, ll _ur, ll _dl, ll _dr){ ul = _ul; ur = _ur; dl = _dl; dr = _dr; } Mat mul(const Mat &m){ Mat ret; ret.ul = pp(mm(ul, m.ul), mm(ur, m.dl)); ret.ur = pp(mm(ul, m.ur), mm(ur, m.dr)); ret.dl = pp(mm(dl, m.ul), mm(dr, m.dl)); ret.dr = pp(mm(dl, m.ur), mm(dr, m.dr)); return ret; } }; ll R(ll i){ if(i == f){ return tt; } if(i == t){ return t; } Mat ret(t, f, f, t); Mat two(t, t, t, f); Mat las(t, f, tt, f); ll x = mn(i, t); while(x){ if(x&t){ ret = ret.mul(two); } two = two.mul(two); x >>= t; } ret = ret.mul(las); return ret.ul; } int main(){ ll C; cin >> C; for(int i=f; i<C; ad(i, t)){ ll N; cin >> N; cout << R(N) << endl; } return f; }