結果
問題 |
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 |
ソースコード
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); }