結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2020-03-11 21:29:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,138 bytes |
コンパイル時間 | 1,930 ms |
コンパイル使用メモリ | 133,276 KB |
最終ジャッジ日時 | 2025-01-09 06:20:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <iostream>#include <vector>#include <limits.h>#include <algorithm>#include <string>#include <math.h>#include <limits.h>#include <queue>#include <map>#include <set>#include <iomanip>#include <bitset>#include <cassert>#include <random>#include <functional>#include <stack>#include <iomanip>#include <cassert>//#include <boost/multiprecision/cpp_int.hpp>#include <complex>#include <cstdio>#include <list>//< in.txt > out.txtusing namespace std;//std::ios::sync_with_stdio(false);//std::cin.tie(0);const long long MOD = 1e9 + 7;typedef long long LL;typedef long double LD;typedef pair<LL, LL> PLL;typedef pair<LD, LL> PDL;typedef pair<LD, LD> PDD;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//typedef boost::multiprecision::cpp_int bigint;template<class T>void in(T& x) {cin >> x;}template<class T1, class T2>void in(pair<T1, T2>& p) {in(p.first);in(p.second);}template<class T>void in(vector<T>& v, LL st = -1, LL en = -1) {if (st == -1) {st = 0;en = v.size() - 1;}for (LL n = st; n <= en; n++) {in(v[n]);}}VVLL modpow(VVLL base, LL p) {if (p == 0) {VVLL res;res.resize(2, VLL(2, 0));res[0][0] = 1;res[1][1] = 1;return res;}if (p == 1) return base;VVLL res = modpow(base, p / 2);VVLL temp;temp.resize(2, VLL(2,0));for (LL x = 0; x < 2; x++) {for (LL y = 0; y < 2; y++) {for (LL k = 0; k < 2; k++) {temp[x][y] += res[x][k] * res[k][y];temp[x][y] %= MOD;}}}if (p % 2 == 0)return temp;VVLL temp2;temp2.resize(2, VLL(2, 0));for (LL x = 0; x < 2; x++) {for (LL y = 0; y < 2; y++) {for (LL k = 0; k < 2; k++) {temp2[x][y] += temp[x][k] * base[k][y];temp2[x][y] %= MOD;}}}return temp2;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);LL a, b, n;cin >> a >> b >> n;if (n == 0) {cout << 0 << "\n";return 0;}else if (n == 1) {cout << 1 << "\n";return 0;}VVLL base;base.resize(2, VLL(2, 0));base[0][0] = a;base[0][1] = b;base[1][0] = 1;base = modpow(base, n - 1);cout << (base[0][0] + MOD) % MOD << "\n";return 0;}