結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
|
提出日時 | 2019-09-21 15:35:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,235 bytes |
コンパイル時間 | 1,305 ms |
コンパイル使用メモリ | 118,996 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 23:57:03 |
合計ジャッジ時間 | 2,112 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<deque>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>using namespace std;typedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;typedef long double ld;const int inf=1e9+7;const ll longinf=1LL<<60 ;const ll mod=1e9+7 ;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef complex<ld> Point;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<int, int> P;typedef pair<ld, ld> LDP;typedef pair<ll, ll> LP;#define fr first#define sc second#define all(c) c.begin(),c.end()#define pb push_back#define debug(x) cout << #x << " = " << (x) << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }//#define int long longtypedef vector<ll> vec;typedef vector<vec> mat;mat mul(mat &A, mat &B) {mat C(A.size(), vec(B[0].size()));for(int i = 0; i < A.size(); i++) {for(int j = 0; j < B[0].size(); j++) {for(int k = 0; k < B.size(); k++) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;}}return C;}mat pow(mat A, ll n) {mat B(A.size(), vec(A.size()));for(int i = 0; i < A.size(); i++) B[i][i] = 1;if(n == 0) return B;mat C(A.size(), vec(A.size()));C = pow(mul(A, A), n / 2);if(n & 1) C = mul(C, A);return C;}void solve() {ll a, b, n; cin >> a >> b >> n;mat A(2, vec(2));A[0][0] = a; A[0][1] = b;A[1][0] = 1; A[1][1] = 0;A = pow(A, n);cout << A[1][0] << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(10);//init();solve();//cout << "finish" << endl;return 0;}