結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-06-14 01:27:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 1,597 ms |
コンパイル使用メモリ | 159,448 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 12:40:32 |
合計ジャッジ時間 | 3,138 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; class matrix { public: long x11, x12, x21, x22; }; matrix mul(matrix, matrix); const long m = 1000000007; long det; int main() { long a, b, n; cin >> a >> b >> n; matrix cache, x; cache.x11 = a; cache.x12 = b; cache.x21 = 1; cache.x22 = 0; x.x11 = 1; x.x12 = 0; x.x21 = 0; x.x22 = 1; while (n > 0) { if (n % 2 == 1) { x = mul(x, cache); } cache = mul(cache, cache); n /= 2; } cout << x.x21 << endl; } matrix mul(matrix x, matrix y) { matrix z; z.x11 = (x.x11 * y.x11 % m + x.x12 * y.x21 % m) % m; z.x12 = (x.x11 * y.x12 % m + x.x12 * y.x22 % m) % m; z.x21 = (x.x21 * y.x11 % m + x.x22 * y.x21 % m) % m; z.x22 = (x.x21 * y.x12 % m + x.x22 * y.x22 % m) % m; return z; }