結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:53:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,065 bytes |
コンパイル時間 | 789 ms |
コンパイル使用メモリ | 77,168 KB |
最終ジャッジ日時 | 2025-01-07 18:48:51 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <iostream>#include <vector>using namespace std;typedef long long ll;typedef vector<vector<ll>> vvl;ll n,mod = 1000000007;vvl mul(const vvl &a,const vvl &b){vvl c(n,vector<ll>(n,0));int i,j,k;for(i=0;i<n;i++){for(j=0;j<n;j++){ll x = 0;for(k=0;k<n;k++){(x += a[i][k]*b[k][j]) %= mod;}c[i][j] = x;}}return c;}vvl pw(const vvl &a, ll x){vvl ret(n,vector<ll>(n,0)),b(n,vector<ll>(n,0));int i,j,k;for(i=0;i<n;i++){ret[i][i] = 1;}for(i=0;i<n;i++){for(j=0;j<n;j++){b[i][j] = a[i][j];}}while(x){while(!(x&1)){b = mul(b,b);x /= 2;}ret = mul(ret,b);x--;}return ret;}vector<ll> mul2(const vvl &a, const vector<ll> &b){vector<ll> c(n,0);int i,j;for(i=0;i<n;i++){ll x = 0;for(j=0;j<n;j++){(x += a[i][j]*b[j]) %= mod;}c[i] = x;}return c;}int main(){long long a,b,x;cin >> a >> b >> x;n = 2;vector<ll> v(2,0);v[0] = 1;vvl m(2,vector<ll>(2,0));m[0][0] = a; m[0][1] = b; m[1][0] = 1;m = pw(m,x);cout << mul2(m,v)[1] << endl;}