結果
問題 |
No.891 隣接3項間の漸化式
|
ユーザー |
![]() |
提出日時 | 2019-05-07 00:44:24 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 703 bytes |
コンパイル時間 | 1,517 ms |
コンパイル使用メモリ | 159,828 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 12:40:49 |
合計ジャッジ時間 | 2,543 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; class mixed { public: long re, im; }; mixed mul(mixed, mixed); const long m = 1000000007; long det; int main() { long a, b, n; cin >> a >> b >> n; long ahalf = a % 2 == 0 ? a / 2 : (a + m) / 2; det = (ahalf * ahalf % m + b) % m; mixed alpha, x, cache; alpha.re = ahalf; alpha.im = 1; x.re = 1; x.im = 0; cache = alpha; while (n > 0) { if (n % 2 == 1) { x = mul(x, cache); } cache = mul(cache, cache); n /= 2; } cout << x.im << endl; } mixed mul(mixed x, mixed y) { mixed z; z.re = (x.re * y.re % m + det * (x.im * y.im % m) % m) % m; z.im = (x.re * y.im % m + x.im * y.re % m) % m; return z; }