結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー | bayashiko |
提出日時 | 2020-09-17 23:14:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,332 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 188,784 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-22 07:16:29 |
合計ジャッジ時間 | 3,390 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 1 ms
6,944 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 1 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,944 KB |
testcase_35 | AC | 2 ms
6,944 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,940 KB |
testcase_38 | AC | 2 ms
6,944 KB |
testcase_39 | AC | 2 ms
6,944 KB |
testcase_40 | AC | 2 ms
6,948 KB |
testcase_41 | AC | 2 ms
6,940 KB |
ソースコード
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> //#include<boost/multiprecision/cpp_int.hpp> //#include<boost/multiprecision/cpp_dec_float.hpp> //namespace mp=boost::multiprecision; //#define mulint mp::cpp_int //#define mulfloat mp::cpp_dec_float_100 using namespace std; struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) constexpr int MOD=1000000007; //constexpr int MOD=998244353; #define INF (1<<30) #define LINF (lint)(1LL<<56) #define endl "\n" #define rep(i,n) for(lint (i)=0;(i)<(n);(i)++) #define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--) #define Flag(x) (1<<(x)) #define Flagcount(x) __builtin_popcountll(x) #define pint pair<int,int> #define pdouble pair<double,double> #define plint pair<lint,lint> #define fi first #define se second typedef long long lint; int dx[8]={1,1,0,-1,-1,-1,0,1}; int dy[8]={0,1,1,1,0,-1,-1,-1}; const int MAX_N=2e5+5; //struct edge{lint to,num;}; //vector<int> bucket[MAX_N/1000]; typedef vector<vector<lint>> mat; mat mtx{ {1,1}, {1,0}, }; vector<lint> F{0,1}; //F(1)~F(K)の値 mat mul(mat &A,mat &B){ mat C(A.size(),vector<lint>(B[0].size())); rep(i,A.size()) rep(j,B.size()) rep(k,B[0].size()){ C[i][k]=(C[i][k]+A[i][j]*B[j][k])%MOD; //演算 適宜演算子を変える } return C; } mat powmat(mat A,lint n){ mat B(A.size(),vector<lint>(A.size())); rep(i,A.size()) B[i][i]=1; //単位元 零元が0じゃない時はそこも自分で埋める while(n){ if(n&1) B=mul(B,A); A=mul(A,A); n>>=1; } return B; } mat powmatsum(mat A,lint n){ //A+A^2+...+A^Nを返す mat B(A.size()*2,vector<lint>(A.size()*2)); rep(i,A.size()) rep(j,A.size()) B[i][j]=A[i][j]; rep(i,A.size()) B[A.size()+i][i]=B[A.size()+i][A.size()+i]=1; B=powmat(B,n+1); rep(i,A.size()) B[A.size()+i][i]=(B[A.size()+i][i]-1+MOD)%MOD; mat res(A.size(),vector<lint>(A.size())); rep(i,A.size()) rep(j,A.size()) res[i][j]=B[A.size()+i][j]; return res; } lint calc(lint n,mat A=mtx,vector<lint> f=F){ //F(N)の計算 if(n==0) return 0; A=powmat(A,n-1); lint res=0; //零元 rep(i,A.size()) res=(res+A[A.size()-1][i]*f[A.size()-1-i])%MOD;//演算 適宜演算子を変える return res; } lint calcsum(lint n,mat A=mtx,vector<lint> f=F){ //Σ[i=1..N]F(i)の計算 if(n==0) return 0; mat B(A.size()*2,vector<lint>(A.size()*2)); rep(i,A.size()) rep(j,A.size()) B[i][j]=A[i][j]; rep(i,A.size()) B[A.size()+i][i]=B[A.size()+i][A.size()+i]=1; B=powmat(B,n); rep(i,A.size()) B[A.size()+i][i]=(B[A.size()+i][i]-1+MOD)%MOD; lint res=0; //零元 rep(i,A.size()) res=(res+B[A.size()*2-1][i]*f[A.size()-1-i])%MOD;//演算 適宜演算子を変える return res; } /* 定数項がある場合、定数をXとして {1,0,1,X},//F(N-1),F(N-2),...,F(N-K)の係数,X {1,0,0,0}, {0,1,0,0}, {0,0,0,1}. F{1,f1,f2,f3}; 答えの計算パートが rep(i,A.size()) res=(res+A[A.size()-2][i]*F[A.size()-1-i])%MOD; となる 累乗和のときは rep(i,A.size()) res=(res+B[A.size()*2-2][i]*f[A.size()-1-i])%MOD; */ int main(void){ lint N; cin >> mtx[0][0] >> mtx[0][1] >> N; cout << calc(N+1) << endl; }