結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー TKTYITKTYI
提出日時 2022-08-18 05:36:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,502 bytes
コンパイル時間 1,101 ms
コンパイル使用メモリ 95,584 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-15 15:37:07
合計ジャッジ時間 1,762 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 8 ms
5,376 KB
testcase_02 AC 12 ms
5,376 KB
testcase_03 AC 12 ms
5,376 KB
testcase_04 AC 12 ms
5,376 KB
testcase_05 AC 11 ms
5,376 KB
testcase_06 AC 12 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<cmath>
#include<numeric>
using namespace std;
typedef long long int ll;
const ll zero=false;
const int one=true;
const int two=one<<one;
const int three=two|one;
const int four=two<<one;
const int five=four|one;
const int six=three<<one;
const int seven=six|one;
const int eight=four<<one;
const int nine=eight|one;
const int ten=five<<one;
ll product(ll A,ll B){vector<ll>a={A},b={B};return inner_product(a.begin(),a.end(),b.begin(),zero);}
ll add(ll A,ll B){vector<ll>v={A,B};return accumulate(v.begin(),v.end(),zero);}
#define FOR(i,l,r) for(ll i=l;i<r;i=add(i,one))
#define REP(i,n) FOR(i,zero,n)
int minu=zero;
const int mod=add(pow(ten,nine),seven);
ll remainder(ll N){
  ll l=zero,r=mod;
  while(r!=add(l,one)){
    ll m=add(l,r)>>one;
    if(product(m,mod)<=N)l=m;
    else r=m;
  }
  N=add(N,product(minu,product(l,mod)));
  while(N>=mod)N=add(N,product(minu,mod));
  return N;
}
vector<vector<ll>>P(vector<vector<ll>>A,vector<vector<ll>>B){
  vector<vector<ll>>res(two,vector<ll>(two));
  REP(i,two)REP(j,two)REP(k,two)res[i][j]=remainder(add(res[i][j],product(A[i][k],B[k][j])));
  return res;
}
int main(){
  int T;cin>>T;
  REP(i,product(four,eight))minu=add(minu,one<<i);
  do{
    int N;cin>>N;
    vector<vector<ll>>A={{one,one},{one,zero}},E={{one,zero},{zero,one}};
    while(N){
      if(N&one)E=P(A,E);
      A=P(A,A);
      N>>=one;
    }
    cout<<remainder(add(E[one][zero],product(two,E[one][one])))<<endl;
  }while(T=add(T,minu));
}
0