結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー startcppstartcpp
提出日時 2018-07-27 23:21:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,273 ms / 2,000 ms
コード長 3,945 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 55,072 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 05:04:42
合計ジャッジ時間 10,433 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,257 ms
5,248 KB
testcase_01 AC 284 ms
5,376 KB
testcase_02 AC 820 ms
5,376 KB
testcase_03 AC 266 ms
5,376 KB
testcase_04 AC 1,273 ms
5,376 KB
testcase_05 AC 864 ms
5,376 KB
testcase_06 AC 428 ms
5,376 KB
testcase_07 AC 173 ms
5,376 KB
testcase_08 AC 1,257 ms
5,376 KB
testcase_09 AC 648 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 5 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 8 ms
5,376 KB
testcase_15 AC 13 ms
5,376 KB
testcase_16 AC 14 ms
5,376 KB
testcase_17 AC 13 ms
5,376 KB
testcase_18 AC 14 ms
5,376 KB
testcase_19 AC 17 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 524 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//ちょっとずるい解法(埋め込み), 正攻法が思いつかないので、「通れば正義！」をします。
#include <iostream>
#define int long long
using namespace std;

int fib[2][101] = {
{0, 908460138, 371975563, 967988087, 392460984, 864787550, 4660654, 393241336, 530142919, 662356693, 21, 964730508, 47291577, 897801569, 558994539, 219772980, 173410246, 485645421, 455258545, 777695784, 999999020, 749206315, 405320339, 835338478, 334795872, 805882474, 845057847, 781424045, 72705620, 785941725, 46368, 822572946, 902652630, 841290252, 705599596, 903751015, 108871225, 787424730, 127577343, 283043407, 997821698, 589865503, 170006352, 624019965, 502023354, 717820129, 37994620, 209613911, 931159308, 911018251, 102334155, 453748616, 107048889, 829771610, 699302941, 358703167, 105381649, 360721530, 107935489, 899099104, 192473059, 83949699, 798695907, 376714645, 630738657, 423131148, 9067912, 836474305, 995872758, 831324169, 851432142, 600615566, 354243748, 464640208, 655980397, 754133024, 468426494, 324986415, 86045214, 28665233, 790216554, 687118902, 551848063, 785195740, 538182908, 132616976, 974887031, 889164309, 960002226, 821409901, 8390086, 104796271, 708897480, 631160278, 49423109, 12869153, 711883378, 884291363, 793850486, 365069693, 815449418},
{1, 945351196, 80688602, 800447448, 947746097, 220121405, 539612979, 850278613, 975243705, 442753488, 999999994, 788097308, 762534955, 921932940, 920981438, 298960180, 82905056, 204446108, 454833148, 153695153, 610, 14075594, 80168765, 868704687, 766126632, 728750240, 563849424, 540754388, 647598500, 333574377, 999971350, 550349788, 469533125, 248947065, 71067117, 449778785, 416172205, 380097838, 108037569, 168309240, 1346269, 119484552, 851774521, 430783349, 893718904, 131647019, 876057088, 594647359, 274635799, 755891406, 936754021, 833876317, 497064675, 504235679, 924144696, 362811371, 409144953, 671476492, 984079976, 304794930, 971215059, 688328829, 786185929, 870139913, 671480699, 816218670, 894130268, 845957748, 473605658, 918746996, 416138535, 814668958, 552196928, 599188704, 516262682, 274911412, 566732752, 568509639, 756454266, 514096566, 470273943, 22230418, 260558644, 967991209, 64173422, 262945064, 469430584, 434089415, 973044099, 918714584, 480986305, 140501410, 201546895, 905224802, 467586512, 366670671, 370029961, 29288003, 510473410, 306318294, 0}
};

int latte[101] = {
0, 964927951, 946533617, 509786860, 207105907, 200000007, 371423623, 407794103, 885945115, 73070046, 999999734, 978161894, 287143675, 250793022, 758601952, 200012817, 54967674, 496453263, 726782935, 672638455, 999397937, 838357449, 779553125, 990409271, 27390880, 228284466, 942232496, 264550114, 123981650, 439990192, 671232238, 276715547, 186591601, 582453221, 693070236, 623800565, 452136886, 365644695, 900717152, 385708940, 410141410, 872850958, 28107846, 483840929, 578609710, 499553298, 923868375, 713286550, 758759346, 819634879, 510853745, 105335718, 847424535, 254470054, 298551243, 890320855, 525352914, 857760585, 681148200, 548456798, 44066357, 603077492, 237828250, 131564763, 323979426, 438560380, 530005158, 364311742, 535307981, 624510285, 743595923, 886680257, 39519988, 108960298, 724037382, 12431477, 196023050, 178248829, 743558048, 745732999, 72124658, 300236456, 982785105, 343811684, 626511910, 997709618, 92863609, 30851551, 497292916, 208207434, 435523618, 735173949, 967192012, 683421425, 987738762, 932680483, 753961026, 911124200, 781900333, 768071074, 128493982
};

int T = 100000000;
int mod = 1000000007;
int n;

signed main() {
	int i;
	
	cin >> n;
	
	int a = fib[0][n / T];
	int b = fib[1][n / T];
	int c;
	int d = latte[n / T];
	
	n %= T;
	if (n == 0) { cout << d << endl; return 0; }
	if (n == 1) { cout << (d + b * b) % mod << endl; return 0; }
	
	d = (d + b * b) % mod;
	for (i = 2; i <= n; i++) {
		c = a + b;
		if (c >= mod) c -= mod;
		d += c * c;
		d %= mod;
		a = b;
		b = c;
	}
	cout << d << endl;
	return 0;
}
0