結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー tails
提出日時 2018-07-27 22:50:57
言語 cLay
(20241019-1)
結果
AC  
実行時間 472 ms / 2,000 ms
コード長 947 bytes
コンパイル時間 4,403 ms
コンパイル使用メモリ 174,768 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 13:09:15
合計ジャッジ時間 8,218 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

int tbl[]={
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 ,
};

ll n;
mint a,b,s;
{
	rd(n);
	n%=1d9+8;
	a=tbl[n/1d8*3+0];
	b=tbl[n/1d8*3+1];
	s=tbl[n/1d8*3+2];
	n%=1d8;
	rep(n){
		b+=a;
		a=b-a;
		s+=a*a;
	}
	wt(s);
}
0