結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー merom686merom686
提出日時 2018-07-27 23:24:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 184 ms / 2,000 ms
コード長 5,071 bytes
コンパイル時間 677 ms
コンパイル使用メモリ 73,592 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 05:10:16
合計ジャッジ時間 2,782 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 181 ms
5,248 KB
testcase_01 AC 42 ms
5,376 KB
testcase_02 AC 118 ms
5,376 KB
testcase_03 AC 41 ms
5,376 KB
testcase_04 AC 184 ms
5,376 KB
testcase_05 AC 126 ms
5,376 KB
testcase_06 AC 63 ms
5,376 KB
testcase_07 AC 26 ms
5,376 KB
testcase_08 AC 178 ms
5,376 KB
testcase_09 AC 94 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 76 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

constexpr int P = 1000000007;

int main() {
    ll n;
    cin >> n;

    if (n == 10000000000) {
        cout << 128493982 << endl;
        return 0;
    }

    int p[100][3] = {
        0, 1, 0,
        908460138, 945351196, 964927951,
        371975563, 80688602, 946533617,
        967988087, 800447448, 509786860,
        392460984, 947746097, 207105907,
        864787550, 220121405, 200000007,
        4660654, 539612979, 371423623,
        393241336, 850278613, 407794103,
        530142919, 975243705, 885945115,
        662356693, 442753488, 73070046,
        21, 999999994, 999999734,
        964730508, 788097308, 978161894,
        47291577, 762534955, 287143675,
        897801569, 921932940, 250793022,
        558994539, 920981438, 758601952,
        219772980, 298960180, 200012817,
        173410246, 82905056, 54967674,
        485645421, 204446108, 496453263,
        455258545, 454833148, 726782935,
        777695784, 153695153, 672638455,
        999999020, 610, 999397937,
        749206315, 14075594, 838357449,
        405320339, 80168765, 779553125,
        835338478, 868704687, 990409271,
        334795872, 766126632, 27390880,
        805882474, 728750240, 228284466,
        845057847, 563849424, 942232496,
        781424045, 540754388, 264550114,
        72705620, 647598500, 123981650,
        785941725, 333574377, 439990192,
        46368, 999971350, 671232238,
        822572946, 550349788, 276715547,
        902652630, 469533125, 186591601,
        841290252, 248947065, 582453221,
        705599596, 71067117, 693070236,
        903751015, 449778785, 623800565,
        108871225, 416172205, 452136886,
        787424730, 380097838, 365644695,
        127577343, 108037569, 900717152,
        283043407, 168309240, 385708940,
        997821698, 1346269, 410141410,
        589865503, 119484552, 872850958,
        170006352, 851774521, 28107846,
        624019965, 430783349, 483840929,
        502023354, 893718904, 578609710,
        717820129, 131647019, 499553298,
        37994620, 876057088, 923868375,
        209613911, 594647359, 713286550,
        931159308, 274635799, 758759346,
        911018251, 755891406, 819634879,
        102334155, 936754021, 510853745,
        453748616, 833876317, 105335718,
        107048889, 497064675, 847424535,
        829771610, 504235679, 254470054,
        699302941, 924144696, 298551243,
        358703167, 362811371, 890320855,
        105381649, 409144953, 525352914,
        360721530, 671476492, 857760585,
        107935489, 984079976, 681148200,
        899099104, 304794930, 548456798,
        192473059, 971215059, 44066357,
        83949699, 688328829, 603077492,
        798695907, 786185929, 237828250,
        376714645, 870139913, 131564763,
        630738657, 671480699, 323979426,
        423131148, 816218670, 438560380,
        9067912, 894130268, 530005158,
        836474305, 845957748, 364311742,
        995872758, 473605658, 535307981,
        831324169, 918746996, 624510285,
        851432142, 416138535, 743595923,
        600615566, 814668958, 886680257,
        354243748, 552196928, 39519988,
        464640208, 599188704, 108960298,
        655980397, 516262682, 724037382,
        754133024, 274911412, 12431477,
        468426494, 566732752, 196023050,
        324986415, 568509639, 178248829,
        86045214, 756454266, 743558048,
        28665233, 514096566, 745732999,
        790216554, 470273943, 72124658,
        687118902, 22230418, 300236456,
        551848063, 260558644, 982785105,
        785195740, 967991209, 343811684,
        538182908, 64173422, 626511910,
        132616976, 262945064, 997709618,
        974887031, 469430584, 92863609,
        889164309, 434089415, 30851551,
        960002226, 973044099, 497292916,
        821409901, 918714584, 208207434,
        8390086, 480986305, 435523618,
        104796271, 140501410, 735173949,
        708897480, 201546895, 967192012,
        631160278, 905224802, 683421425,
        49423109, 467586512, 987738762,
        12869153, 366670671, 932680483,
        711883378, 370029961, 753961026,
        884291363, 29288003, 911124200,
        793850486, 510473410, 781900333,
        365069693, 306318294, 768071074,
    };

    ll k = n / 100000000, m = n % 100000000;
    ll f0, f1 = p[k][0], f2 = p[k][1];
    ll s = p[k][2];
    for (int i = 0; i < m; i++) {
        s += f2 * f2 % P;
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
        if (f2 >= P) f2 -= P;
    }
    s %= P;
    cout << s << endl;

    //ll f0, f1 = 0, f2 = 1;
    //ll s = 0;
    //for (int j = 0; j < 100; j++) {
    //    cout << f1 << ", " << f2 << ", " << s << ", " << '\n';
    //    for (int i = 0; i < 100000000; i++) {
    //        s += f2 * f2 % P;
    //        f0 = f1;
    //        f1 = f2;
    //        f2 = f0 + f1;
    //        if (f2 >= P) f2 -= P;
    //    }
    //    s %= P;
    //}

    return 0;
}
0