結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー FF256grhyFF256grhy
提出日時 2018-07-27 22:56:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,594 ms / 2,000 ms
コード長 5,450 bytes
コンパイル時間 1,559 ms
コンパイル使用メモリ 163,584 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-18 12:36:22
合計ジャッジ時間 14,050 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,572 ms
4,376 KB
testcase_01 AC 352 ms
4,376 KB
testcase_02 AC 1,027 ms
4,384 KB
testcase_03 AC 337 ms
4,380 KB
testcase_04 AC 1,594 ms
4,376 KB
testcase_05 AC 1,076 ms
4,380 KB
testcase_06 AC 537 ms
4,380 KB
testcase_07 AC 215 ms
4,376 KB
testcase_08 AC 1,545 ms
4,380 KB
testcase_09 AC 813 ms
4,380 KB
testcase_10 AC 5 ms
4,376 KB
testcase_11 AC 4 ms
4,376 KB
testcase_12 AC 5 ms
4,376 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 10 ms
4,376 KB
testcase_15 AC 15 ms
4,380 KB
testcase_16 AC 17 ms
4,380 KB
testcase_17 AC 15 ms
4,380 KB
testcase_18 AC 16 ms
4,376 KB
testcase_19 AC 22 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 655 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(LL i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL MOD = 1e9 + 7;

LL x[] = {
0, 1, 0, 
908460138, 945351196, 407047619, 
371975563, 80688602, 445927374, 
967988087, 800447448, 494873801, 
392460984, 947746097, 323037012, 
864787550, 220121405, 800000021, 
4660654, 539612979, 675867961, 
393241336, 850278613, 151200436, 
530142919, 975243705, 287465138, 
662356693, 442753488, 382188499, 
21, 999999994, 999999293, 
964730508, 788097308, 427158452, 
47291577, 762534955, 47652197, 
897801569, 921932940, 594264825, 
558994539, 920981438, 314103675, 
219772980, 298960180, 800033558, 
173410246, 82905056, 847684956, 
485645421, 204446108, 209146333, 
455258545, 454833148, 382088297, 
777695784, 153695153, 454938895, 
999999020, 610, 998423768, 
749206315, 14075594, 331648910, 
405320339, 80168765, 722470236, 
835338478, 868704687, 47585356, 
334795872, 766126632, 903768428, 
805882474, 728750240, 874049696, 
845057847, 563849424, 164816400, 
781424045, 540754388, 434752827, 
72705620, 647598500, 981400006, 
785941725, 333574377, 667945304, 
46368, 999971350, 521240828, 
822572946, 550349788, 521980360, 
902652630, 469533125, 444147056, 
841290252, 248947065, 426614698, 
705599596, 71067117, 302802522, 
903751015, 449778785, 227631577, 
108871225, 416172205, 902106869, 
787424730, 380097838, 290335702, 
127577343, 108037569, 567709349, 
283043407, 168309240, 700336281, 
997821698, 1346269, 380075144, 
589865503, 119484552, 678997112, 
170006352, 851774521, 510075062, 
624019965, 430783349, 491046102, 
502023354, 893718904, 381392516, 
717820129, 131647019, 508836795, 
37994620, 876057088, 785029112, 
209613911, 594647359, 336136566, 
931159308, 274635799, 953124039, 
911018251, 755891406, 974215614, 
102334155, 936754021, 304595673, 
453748616, 833876317, 24634897, 
107048889, 497064675, 291506462, 
829771610, 504235679, 312124394, 
699302941, 924144696, 430473962, 
358703167, 362811371, 775166693, 
105381649, 409144953, 657130757, 
360721530, 671476492, 563059832, 
107935489, 984079976, 977029569, 
899099104, 304794930, 393508333, 
192473059, 971215059, 862570029, 
83949699, 688328829, 690219755, 
798695907, 786185929, 844681637, 
376714645, 870139913, 367486199, 
630738657, 671480699, 674634534, 
423131148, 816218670, 284042245, 
9067912, 894130268, 502541003, 
836474305, 845957748, 336903523, 
995872758, 473605658, 351119218, 
831324169, 918746996, 498668807, 
851432142, 416138535, 387444568, 
600615566, 814668958, 290353286, 
354243748, 552196928, 920852915, 
464640208, 599188704, 729910688, 
655980397, 516262682, 487931719, 
754133024, 274911412, 106063199, 
468426494, 566732752, 450854667, 
324986415, 568509639, 983009794, 
86045214, 756454266, 943078705, 
28665233, 514096566, 168540575, 
790216554, 470273943, 227585128, 
687118902, 22230418, 119477526, 
551848063, 260558644, 477687110, 
785195740, 967991209, 545390506, 
538182908, 64173422, 190661326, 
132616976, 262945064, 797435876, 
974887031, 469430584, 533701667, 
889164309, 434089415, 165696211, 
960002226, 973044099, 23567709, 
821409901, 918714584, 470377180, 
8390086, 480986305, 892928980, 
104796271, 140501410, 396544314, 
708897480, 201546895, 334591043, 
631160278, 905224802, 946927199, 
49423109, 467586512, 301611382, 
12869153, 366670671, 834902379, 
711883378, 370029961, 428715722, 
884291363, 29288003, 708524894, 
793850486, 510473410, 70854260, 
365069693, 306318294, 953887985, 
815449418, 923369890, 466659501
};


int main() {
	/*
	LL a = 0, b = 1, s = 0;
	incII(i, 0, 10000000000LL) {
		LL c = (a + b) % MOD;
		if(i % 100000000 == 0) { cout << a << ", " << b << ", " << s << ", " << endl; }
		(s += a * a) %= MOD;
		a = b; b = c;
	}
	cout << "END" << endl;
	*/
	
	
	LL n;
	cin >> n;
	n++;
	
	LL p = n / 100000000;
	LL a = x[3 * p + 0];
	LL b = x[3 * p + 1];
	LL s = x[3 * p + 2];
	
	inc(i, n - p * 100000000LL) {
		
		LL c = (a + b) % MOD;
		(s += a * a) %= MOD;
		// cout << a << endl;
		a = b; b = c;
	}
	
	cout << s << endl;
	
	return 0;
}
0