結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2020-09-17 23:14:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#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_100using 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 secondtypedef 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;}