結果

問題 No.8037 Restricted Lucas (Hard)
ユーザー kurenai3110
提出日時 2018-04-02 01:21:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 641 ms
コンパイル使用メモリ 65,996 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:26:30
合計ジャッジ時間 1,326 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int zero = false;
const int one = true;
ll add(ll a, ll b)
{
    while (b != zero)
    {
        ll c = (a & b) << one;
        a ^= b;
        b = c;
    }
    return a;
}
ll sub(ll a, ll b)
{
    while (b != zero)
    {
        ll c = (~a & b) << one;
        a ^= b;
        b = c;
    }
    return a;
}
const int two = add(one, true);
const int three = add(two, true);
const int four = add(three, true);
const int five = add(four, true);
const int six = add(five, true);
const int seven = add(six, true);
const int eight = add(seven, true);
const int nine = add(eight, true);
const int ten = add(nine, true);
ll product(ll a, ll b) {
    if (b == zero)return zero;
    ll cnt = one;
    ll ret = a;
    while (b >= add(cnt, cnt)) {
        ret = add(ret, ret);
        cnt = add(cnt, cnt);
    }
    return add(ret, product(a, sub(b, cnt)));
}
const int MOD = add(product(product(product(product(product(product(product(product(ten, ten), ten), ten), ten), ten), ten), ten), ten), seven);
ll mod(ll a, ll b) {
    while (a >= b) {
        ll m = b;
        while (a >= add(m, m))m = add(m, m);
        a = sub(a, m);
    }
    return a;
}
vector<vector<ll>> mul(vector<vector<ll>>&a, vector<vector<ll>>&b, ll p) {
    vector<vector<ll>>c(a.size(), vector<ll>(b.size()));
    
    for (ll i = zero; i<a.size(); i=add(i ,one)) {
        for (ll k = zero; k<b.size(); k=add(k, one)) {
            for (ll j = zero; j<b[zero].size(); j = add(j, one)) {
                c[i][j] = mod((add(c[i][j], product(a[i][k],b[k][j]))), p);
            }
        }
    }
    return c;
}
vector<vector<ll>> pow(vector<vector<ll>>&a, ll n, ll p) {
    vector<vector<ll>>b(a.size(), vector<ll>(a.size()));
    for (ll i = zero; i<a.size(); i = add(i, one)) {
        b[i][i] = one;
    }
    while (n>zero) {
        if (n & one) b = mul(a, b, p);
        a = mul(a, a, p);
        n >>= one;
    }
    return b;
}
ll fibonacci(ll n, ll p) {
    vector<vector<ll>>a(two, vector<ll>(two));
    a[zero][zero] = one; a[zero][one] = one;
    a[one][zero] = one; a[one][one] = zero;
    a = pow(a, add(n, one), p);
    return a[one][zero];
}
int main() {
    int T; cin >> T;
    for (int i = zero; i < T; i = add(i, one)) {
        int N; cin >> N;
        
        cout << mod(add(fibonacci(sub(N, two), MOD), fibonacci(N, MOD)), MOD) << endl;
    }
    return zero;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0