結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー mtsdmtsd
提出日時 2018-04-02 12:51:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 3,457 bytes
コンパイル時間 756 ms
コンパイル使用メモリ 83,796 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-08 13:21:11
合計ジャッジ時間 1,439 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <numeric>
using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back

ll mod;

ll zero(){
    ll a = (ll)false;
    return a;
}

ll one(){
    ll a = (ll)true;
    return a;
}

ll add(ll a,ll b){
    vector<ll>v;
    v.PB(a);
    v.PB(b);
    return accumulate(v.begin(),v.end(),zero());
}

ll two(){
    ll a = (ll)true;
    return add(a,a);
}
ll three(){
    return add(two(),one());
}
ll seven(){
    ll a = three();
    a = add(a,a);
    a = add(a,one());
    return a;
}
ll nine(){
    return add(two(),seven());
}
ll ten(){
    return add(three(),seven());
}



ll divide(ll a,ll b){
    lldiv_t c = div(a,b);
    return c.quot;
}
ll modulo(ll a,ll b){
    lldiv_t c = div(a,b);
    return c.rem;
}

ll mul(ll a,ll b){
    if(b==zero())return zero();
    if(b==one())return a;
    if(modulo(b,two())==zero()){
        ll c = mul(a,divide(b,two()));
        return modulo(add(c,c),mod);
    }else{
        ll c = mul(a,divide(b,two()));
        return modulo(add(c,add(c,a)),mod);
    }
}

ll mult(ll a,ll b){
    if(b==zero())return zero();
    if(b==one())return a;
    if(modulo(b,two())==zero()){
        ll c = mult(a,divide(b,two()));
        return add(c,c);
    }else{
        ll c = mult(a,divide(b,two()));
        return add(c,add(c,a));
    }
}
void mod_calc(){
    mod = one();
    for(ll i=zero();i<nine();i=add(i,one())){
        mod = mult(mod,ten());
    }
    mod = add(mod,seven());
    return;
}

vector<vector<ll> > mat_mul(vector<vector<ll> > &v,vector<vector<ll> > &w){
    vector<vector<ll> > z(two(),vector<ll>(two()));
    z[zero()][zero()] = modulo(add(mul(v[zero()][zero()],w[zero()][zero()]),mul(v[zero()][one()],w[one()][zero()])),mod);
    z[zero()][one()] = modulo(add(mul(v[zero()][zero()],w[zero()][one()]),mul(v[zero()][one()],w[one()][one()])),mod);
    z[one()][zero()] = modulo(add(mul(v[one()][zero()],w[zero()][zero()]),mul(v[one()][one()],w[one()][zero()])),mod);
    z[one()][one()] = modulo(add(mul(v[one()][zero()],w[zero()][one()]),mul(v[one()][one()],w[one()][one()])),mod);
    return z;
}

vector<vector<ll> > mat_calc(vector<vector<ll> > &v,ll n){
    if(n==zero()){
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z[zero()][zero()]=one();
        z[one()][one()]=one();
        return z;
    }
    if(n==one())return v;
    if(modulo(n,two())==zero()){
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z = mat_calc(v,divide(n,two()));
        return mat_mul(z,z);
    }else{
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z = mat_calc(v,divide(n,two()));
        z = mat_mul(z,z);
        return mat_mul(z,v);
    }
}

ll calc(ll n){
    vector<vector<ll> > v(two(),vector<ll>(two()));
    v[zero()][zero()] = zero();
    v[zero()][one()] = one();
    v[one()][zero()] = one();
    v[one()][one()] = one();
    vector<vector<ll> > z(two(),vector<ll>(two()));
    z = mat_calc(v,n);
    
    return modulo(add(mul(z[zero()][zero()],two()),mul(z[zero()][one()],one())),mod);
}

int main(){
    mod_calc();
    int t;
    cin >> t;
    for(int i=zero();i<t;i=add(i,one())){
        ll n;
        cin >> n;
        cout << calc(n) << endl;
    }
    return zero();
}
0