結果

問題 No.3225 2×2行列相似判定 〜easy〜
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-07-15 14:43:29
言語 D
(dmd 2.109.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 607 bytes
コンパイル時間 769 ms
コンパイル使用メモリ 86,444 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-07-27 20:09:52
合計ジャッジ時間 2,039 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.algorithm, std.array, std.conv, std.typecons;

immutable p = 1000000007;

void main() {
	auto N = readln[0 .. $-1].to!ulong;
	auto M = Matrix(1, 0, 0, 1);
	auto A = Matrix(1, 1, 1, 0);
	auto power = 1UL;
	
	while (power <= N) {
		if ((N & power) != 0) M = multiply(A, M);
		A = multiply(A, A);
		power *= 2;
	}
	
	writeln((M[2] + M[3]) % p);
	
}

// 0 1
// 2 3
alias Matrix = Tuple!(ulong, ulong, ulong, ulong);

Matrix multiply(Matrix a, Matrix b) {
	return Matrix( (a[0]*b[0] + a[1]*b[2]) % p, (a[0]*b[1] + a[1]*b[3]) % p, (a[2]*b[0] + a[3]*b[2]) % p, (a[2]*b[1] + a[3]*b[3]) % p);
}
0