結果

問題 No.8036 Restricted Lucas (Easy)
ユーザー ats5515
提出日時 2018-04-02 00:39:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 2,339 bytes
コンパイル時間 897 ms
コンパイル使用メモリ 90,556 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:23:43
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD;
int zero;
int one;
int two;
int add(int a, int b)
{
    while (b != zero)
    {
        int c = (a & b) << one;
        a ^= b;
        b = c;
    }
    return a;
}
int sub(int a, int b)
{
    return add(a, add(~b, one));
}
int mul(int a, int b)
{
    int c = zero;
    while (b != zero)
    {
        if (b & one)
            c = add(c, a);
        b >>= one;
        a <<= one;
    }
    return c;
}
int msb(int a)
{
    int c = zero;
    while (a != zero)
    {
        a >>= one;
        c = add(c, one);
    }
    return c;
}
int mydiv(int a, int b)
{
    int q = zero;
    int c = sub(msb(a), msb(b));
    for (; c >= zero; c = sub(c, one))
    {
        int d = sub(a, b << c);
        if (d >= zero)
        {
            a = d;
            q |= one << c;
        }
    }
    return a;
}
void initmod() {
    int ten = mul(two, add(two, add(two, one)));
    MOD = one;
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = mul(MOD, ten);
    MOD = add(MOD, sub(ten, add(two, one)));
}
using Mat = vector<vector<int> >;
Mat matmul(Mat a, Mat b) {
    Mat res(two, vector<int>(two, zero));
    res[zero][zero] = add(mydiv(mul(a[zero][zero], b[zero][zero]), MOD), mydiv(mul(a[zero][one], b[one][zero]), MOD));
    res[one][zero] = add(mydiv(mul(a[one][zero], b[zero][zero]), MOD), mydiv(mul(a[one][one], b[one][zero]), MOD));
    res[zero][one] = add(mydiv(mul(a[zero][zero], b[zero][one]), MOD), mydiv(mul(a[zero][one], b[one][one]), MOD));
    res[one][one] = add(mydiv(mul(a[one][zero], b[zero][one]), MOD), mydiv(mul(a[one][one], b[one][one]), MOD));
    return res;
}
Mat matpow(Mat a, int b) {
    if (b == one)return a;
    if ((b & one) == zero) {
        return matpow(matmul(a, a), b >> one);
    }
    else {
        return matmul(matpow(matmul(a, a), b >> one), a);
    }
}
signed main() {
    int N;
    cin >> N;
    zero = N^N;
    one = abs(~zero);
    two = add(one, one);
    initmod();
    vector<int> A(N);
    Mat k(two, vector<int>(two));
    k[zero][zero] = one;
    k[zero][one] = one;
    k[one][zero] = one;
    k[one][one] = zero;
    for (int i = zero; i < N; i = add(i, one)) {
        cin >> A[i];
        Mat x = matpow(k, A[i]);
        cout << mydiv(add(x[one][zero], mul(x[one][one], two)), MOD) << endl;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0