結果

問題 No.8036 Restricted Lucas (Easy)
ユーザー TKTYITKTYI
提出日時 2022-08-18 05:11:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 1,251 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 93,136 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-05 13:59:44
合計ジャッジ時間 1,532 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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