피보나치 수열 행렬 곱셈 최적화 DP
피보나치 수열 행렬 곱셈 최적화 DP
\(f (n)\%1000000007\),\(n\le 10^ {18}\)
행렬 곱하기:\(i\times k\)의 행렬\(A\) 곱하기\(k\times j\)의 행렬\(B\)는\(k\times k\)의 행렬을 받습니다. 그 중에서 제\(i\) 열 제\(j\) 줄의 수는\(A\)의 제\(i\) 줄의 모든 수와\(B\)의 제\(j\) 열을 각각 곱하고 덧붙입니다.
매트릭스 곱셈을 사용하여 DP를 최적화하는 것을 고려하여\(f(n)\)를 얻기 위해 매트릭스\(\text{base}\)를 설정하여\(\begin{bmatrix} F {n-1} & F {n-2}\end{bmatrix}\times base =\begin{bmatrix} F {n} & F {n-1}\end{bmatrix}\)를 쉽게 추측할 수 있도록\(base=\begin{bmatrix} {bmat1} &\\{bmatrix}\1 &\{bmandx} {bmatrix}\1
그리고 행렬 곱셈은 빠른 멱 최적화를 사용할 수 있기 때문에\(base^{n-2}\)를 직접 계산합니다. 답은 $\begin{bmatrix} 1 & 1\end{bmatrix}\times base^{n-2} $행렬의 첫 번째 줄 첫 번째 열입니다.
#include
#include
#define MOD 1000000007
using namespace std;
long long n;
struct Mat{
long long a[3][3];
Mat(){memset(a, 0, sizeof a);}
Mat operator * (const Mat &b) const{
Mat res;
for(int i=1;i<=2;++i)
for(int j=1;j<=2;++j)
for(int k=1;k<=2;++k)
res.a[i][j]=(res.a[i][j] + (a[i][k] * b.a[k][j])%MOD)%MOD;
return res;
}
} ans, base;
void qpow(long long x){
while(x!=0){
if(x&1) ans=ans*base;
x>>=1;
base=base*base;
}
}
int main(){
scanf("%lld", &n);
if(n<=2){
puts("1");
return 0;
}
ans.a[1][1]=ans.a[1][2]=1;
base.a[1][1]=1,base.a[1][2]=1,base.a[2][1]=1,base.a[2][2]=0;
qpow(n-2);
printf("%lld", ans.a[1][1]);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
