結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー parukiparuki
提出日時 2018-08-17 22:34:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 998 ms / 2,000 ms
コード長 5,304 bytes
コンパイル時間 2,093 ms
コンパイル使用メモリ 202,812 KB
実行使用メモリ 6,816 KB
最終ジャッジ日時 2024-10-10 22:27:32
合計ジャッジ時間 10,113 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 982 ms
5,248 KB
testcase_01 AC 221 ms
5,248 KB
testcase_02 AC 641 ms
5,248 KB
testcase_03 AC 212 ms
5,248 KB
testcase_04 AC 998 ms
5,248 KB
testcase_05 AC 674 ms
5,248 KB
testcase_06 AC 337 ms
5,248 KB
testcase_07 AC 136 ms
5,248 KB
testcase_08 AC 965 ms
5,248 KB
testcase_09 AC 509 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 4 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 6 ms
5,248 KB
testcase_15 AC 9 ms
5,248 KB
testcase_16 AC 10 ms
5,248 KB
testcase_17 AC 9 ms
5,248 KB
testcase_18 AC 10 ms
5,248 KB
testcase_19 AC 12 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 359 ms
5,248 KB
testcase_22 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

const int MOD = (int)1e9 + 7;
int add(int a, int b) {
    int c = a + b;
    if (c >= MOD)c -= MOD;
    else if (c < 0)c += MOD;
    return c;
}

int mul(int a, int b) {
    return (int)((long long)a*b%MOD);
}

const int MAGIC[101][3] = {
    { 0,0,0 },
{ 36891058,908460138,964927951 },
{ 708713046,371975563,946533617 },
{ 832459368,967988087,509786860 },
{ 555285113,392460984,207105907 },
{ 355333862,864787550,200000007 },
{ 534952325,4660654,371423623 },
{ 457037277,393241336,407794103 },
{ 445100786,530142919,885945115 },
{ 780396802,662356693,73070046 },
{ 999999973,21,999999734 },
{ 823366807,964730508,978161894 },
{ 715243378,47291577,287143675 },
{ 24131371,897801569,250793022 },
{ 361986899,558994539,758601952 },
{ 79187200,219772980,200012817 },
{ 909494817,173410246,54967674 },
{ 718800694,485645421,496453263 },
{ 999574610,455258545,726782935 },
{ 375999376,777695784,672638455 },
{ 1597,999999020,999397937 },
{ 264869286,749206315,838357449 },
{ 674848433,405320339,779553125 },
{ 33366209,835338478,990409271 },
{ 431330760,334795872,27390880 },
{ 922867773,805882474,228284466 },
{ 718791584,845057847,942232496 },
{ 759330350,781424045,264550114 },
{ 574892880,72705620,123981650 },
{ 547632659,785941725,439990192 },
{ 999924982,46368,671232238 },
{ 727776849,822572946,276715547 },
{ 566880502,902652630,186591601 },
{ 407656820,841290252,582453221 },
{ 365467528,705599596,693070236 },
{ 546027777,903751015,623800565 },
{ 307300980,108871225,452136886 },
{ 592673115,787424730,365644695 },
{ 980460233,127577343,900717152 },
{ 885265840,283043407,385708940 },
{ 3524578,997821698,410141410 },
{ 529619056,589865503,872850958 },
{ 681768169,170006352,28107846 },
{ 806763391,624019965,483840929 },
{ 391695550,502023354,578609710 },
{ 413826897,717820129,499553298 },
{ 838062468,37994620,923868375 },
{ 385033448,209613911,713286550 },
{ 343476498,931159308,758759346 },
{ 844873162,911018251,819634879 },
{ 834419866,102334155,510853745 },
{ 380127701,453748616,105335718 },
{ 390015786,107048889,847424535 },
{ 674464076,829771610,254470054 },
{ 224841755,699302941,298551243 },
{ 4108204,358703167,890320855 },
{ 303763304,105381649,525352914 },
{ 310754962,360721530,857760585 },
{ 876144487,107935489,681148200 },
{ 405695833,899099104,548456798 },
{ 778742000,192473059,44066357 },
{ 604379130,83949699,603077492 },
{ 987490029,798695907,237828250 },
{ 493425268,376714645,131564763 },
{ 40742042,630738657,323979426 },
{ 393087522,423131148,438560380 },
{ 885062356,9067912,530005158 },
{ 9483443,836474305,364311742 },
{ 477732907,995872758,535307981 },
{ 87422827,831324169,624510285 },
{ 564706400,851432142,743595923 },
{ 214053392,600615566,886680257 },
{ 197953180,354243748,39519988 },
{ 134548496,464640208,108960298 },
{ 860282292,655980397,724037382 },
{ 520778395,754133024,12431477 },
{ 98306258,468426494,196023050 },
{ 243523224,324986415,178248829 },
{ 670409052,86045214,743558048 },
{ 485431333,28665233,745732999 },
{ 680057396,790216554,72124658 },
{ 335111523,687118902,300236456 },
{ 708710588,551848063,982785105 },
{ 182795469,785195740,343811684 },
{ 525990521,538182908,626511910 },
{ 130328088,132616976,997709618 },
{ 494543560,974887031,92863609 },
{ 544925113,889164309,30851551 },
{ 13041873,960002226,497292916 },
{ 97304683,821409901,208207434 },
{ 472596219,8390086,435523618 },
{ 35705139,104796271,735173949 },
{ 492649422,708897480,967192012 },
{ 274064524,631160278,683421425 },
{ 418163403,49423109,987738762 },
{ 353801518,12869153,932680483 },
{ 658146590,711883378,753961026 },
{ 144996647,884291363,911124200 },
{ 716622931,793850486,781900333 },
{ 941248608,365069693,768071074 },
{ 107920472,815449418,128493982 },

};

void outa(int x, int y, int z) {
    cout << "{" << x << "," << y << "," << z << "}," << endl;
}

void preCalc() {
    const ll N = 10000000000ll;

    // {,},
    // {,},...
    outa(0, 0, 0);
    int a = 0, b = 1, s = 1;
    for (ll i = 2; i <= N; ++i) {
        int c = add(a, b);
        a = b;
        b = c;
        s = add(s, mul(b, b));
        if (i % 100000000 == 0) {
            outa(a, b, s);
        }
    }
}

ll f(ll cur, ll n, int s, int a, int b) {
    for (ll i = cur; i <= n; ++i) {
        int c = add(a, b);
        a = b;
        b = c;
        s = add(s, mul(b, b));
    }
    return s;
}

void solve() {
    const int R = 100000000;
    // preCalc();
    ll N, re = 0;
    cin >> N;
    if (N < R) {
        re = f(2, N, 1, 0, 1);
    } else {
        ll k = N / R;
        ll m = k * R;
        re = f(m + 1, N, MAGIC[k][2], MAGIC[k][0], MAGIC[k][1]);
    }
    cout << re << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}
0