結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー tails
提出日時 2020-10-29 22:08:44
言語 cLay
(20241019-1)
結果
AC  
実行時間 3,802 ms / 5,000 ms
コード長 361 bytes
コンパイル時間 3,682 ms
コンパイル使用メモリ 184,216 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 14:40:38
合計ジャッジ時間 17,153 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 5秒ならなんとか…
{
	ll@n,@k;
	Mint a[1d4];
	rd(a(n));

	Polynomial<Mint> b,c,m;
	b.change(0,1);
	c.change(1,1);
	m.change(0,1);
	m.change(n,-2);
	m.change(n+1,1);

	for(int j=40;j>=0;--j){
		b*=b;
		b%=m;
		if(k-n&1l<<j){
			b*=c;
			b%=m;
		}
	}

	Mint x,y,z;
	rrep(i,n){
		x+=a[i];
		y-=x*b.c[0];
		b*=c;
		b%=m;
		z-=x*b.c[0];
	}
	wt(z-y,z+x);
}
0