結果
問題 | No.3037 Restricted Lucas (Hard) |
ユーザー | kmjp |
提出日時 | 2018-04-01 23:13:39 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 2,643 bytes |
コンパイル時間 | 805 ms |
コンパイル使用メモリ | 74,548 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-26 06:06:39 |
合計ジャッジ時間 | 1,459 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,812 KB |
testcase_01 | AC | 12 ms
6,940 KB |
testcase_02 | AC | 18 ms
6,940 KB |
testcase_03 | AC | 17 ms
6,944 KB |
testcase_04 | AC | 18 ms
6,940 KB |
testcase_05 | AC | 17 ms
6,944 KB |
testcase_06 | AC | 18 ms
6,940 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:148:18: warning: ‘x’ is used uninitialized [-Wuninitialized] 148 | return x&x; | ^
ソースコード
#include <iostream> #include <cstdlib> #include <vector> #include <cmath> using namespace std; typedef signed long long ll; string S; ll mo; ll N; int T; ll momo(ll v) { lldiv_t d; d=div(v,mo); return d.rem; } ll add(ll a,ll b) { long double aa=a; long double bb=b; return fma(aa,aa==aa,bb); } ll sub(ll a,ll b) { int c=a!=a; c=~c; long double aa=a; long double bb=b; return fma(bb,c,aa); } int inc(int& v) { v=add(v,(int)true); return v; } int dec(int& v) { v=sub(v,(int)true); return v; } ll mul(ll x,ll y) { ll r=x!=x,a=x==x; while(y) { if(y&a) { r=momo(add(r,x)); } x<<=a; x=momo(x); y>>=a; } return momo(r); } ll fib(ll k,ll a,ll b) { int z=k&~k; a=z==z; int c=add(a,a); b=add(a,c); if(k==a) return a; if(k==c) return b; k=sub(k,c); vector<ll> V; V.push_back(z); V.push_back(z); vector<vector<ll>> R,A; R.push_back(V); R.push_back(V); A.push_back(V); A.push_back(V); R[z][z]=a; R[z][a]=z; R[a][z]=z; R[a][a]=a; A[z][z]=a; A[z][a]=a; A[a][z]=a; A[a][a]=z; while(k) { if(k&a) { vector<vector<ll>> S; S.push_back(V); S.push_back(V); S[z][z]=momo(add(mul(A[z][z],R[z][z]),mul(A[z][a],R[a][z]))); S[z][a]=momo(add(mul(A[z][z],R[z][a]),mul(A[z][a],R[a][a]))); S[a][z]=momo(add(mul(A[a][z],R[z][z]),mul(A[a][a],R[a][z]))); S[a][a]=momo(add(mul(A[a][z],R[z][a]),mul(A[a][a],R[a][a]))); swap(S,R); } vector<vector<ll>> T; T.push_back(V); T.push_back(V); T[z][z]=momo(add(mul(A[z][z],A[z][z]),mul(A[z][a],A[a][z]))); T[z][a]=momo(add(mul(A[z][z],A[z][a]),mul(A[z][a],A[a][a]))); T[a][z]=momo(add(mul(A[a][z],A[z][z]),mul(A[a][a],A[a][z]))); T[a][a]=momo(add(mul(A[a][z],A[z][a]),mul(A[a][a],A[a][a]))); swap(T,A); k>>=a; } return momo(add(momo(mul(b,R[z][z])),R[z][a])); } void solve() { int i,j,k,l,r,x,y; string s; int c=i!=i; inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); inc(c); S.push_back((char)c); dec(c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); S.push_back((char)c); inc(c);inc(c);inc(c);inc(c);inc(c);inc(c);inc(c); S.push_back((char)c); mo=atoi(S.c_str()); cin>>T; while(T) { dec(T); cin>>N; cout<<fib(N,N,N)<<endl; } } int main(){ int x; solve(); return x&x; }