結果

問題 No.8036 Restricted Lucas (Easy)
ユーザー IL_msta
提出日時 2018-04-02 19:04:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,596 bytes
コンパイル時間 1,079 ms
コンパイル使用メモリ 87,424 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:42:22
合計ジャッジ時間 1,709 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
LL zero = false;
LL one = true;
LL MOD;
LL getMod();
LL kake(LL A,LL B){
LL ret = zero;
vector<LL> keta;
while(B){
    if(B&one){
        keta.push_back(one);
    }else{
        keta.push_back(zero);
    }
    B >>= one;
}
reverse(keta.begin(),keta.end());
int size = keta.size();
for(int i=zero;i<size;++i){
    ret <<= one;
    if( keta[i] ){
        ret += A;
    }
}
return ret;
}
vector<LL> V;
LL ama(LL A){
    int size = V.size();
    for(int i=zero;i<size;++i){
        while( A >= V[i]){
            A -= V[i];
        }
    }
return A;
}
vector< vector<LL> > MUL( vector<vector<LL> >& A,vector< vector<LL> >& B){
    LL mod = MOD;
    int R = A.size();
    int cen = A[zero].size();
    int C = B[zero].size();
    vector< vector<LL> > ans(R,vector<LL>(C,zero) );
    for(int row=zero;row<R;++row){
        for(int col=zero;col<C;++col){
            for(int inner=zero;inner< cen;++inner){
ans[row][col] = (ans[row][col] + kake(A[row][inner],B[inner][col]) );
    ans[row][col] = ama(ans[row][col]);
            }
        }
    }
    return ans;
}
vector< vector<LL> > powMod(const vector< vector<LL> >& mat,LL N,LL mod=MOD){
    int R = mat.size();
    int C = mat[zero].size();
    
    vector< vector<LL> > I(R,vector<LL>(C,zero));
    for(int i=zero;i<R && i<C;++i){
        I[i][i] = one;
    }
    if( N == zero ){
        return I;
    }
    vector< vector<LL> > mul(R,vector<LL>(C)),ans(R,vector<LL>(C));
    ans = I;
    mul = mat;
    while(N){
        if( N & one ){
            ans = MUL(ans,mul);
        }
        N >>= one;
        mul = MUL(mul,mul);
    }
    return ans;
}
signed main() {
    MOD = getMod();
{
    LL temp = MOD;
    while(temp>=zero){
        V.push_back( temp );
        temp <<= one;
    }
    reverse(V.begin(),V.end() );
}
    int T;
    cin>>T;
    vector< vector<LL> > R(one<<one,vector<LL>(one<<one,one));
    R[one][one] = zero;
    vector<vector<LL> > A(one<<one,vector<LL>(one));
    A[zero][zero] = one;
    A[one][zero] = one<<one;
    while(T--){
        LL N;
        cin>>N;
        if( N== one){
            cout << one << endl;
            continue;
        }
        vector<vector<LL> > res = powMod(R,N-one);
        vector<vector<LL> > ans = MUL(res,A);
        cout << ans[zero][zero] << endl;
    }
}
LL getMod(){
    long long MOD = zero;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
    return MOD;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0