소 객 프로 그래 밍 리 즈 S1 7 차 전 - 황금 & 다이아몬드 C. 수열 값 구하 기
제목 링크
제목 설명
이미 알 고 있 는 a 0 = 0, a 1 = 1, a i = b a i - 1 + c a i - 2 (i ≥ 2) a0=0,a_1=1,a_i=b a_{i-1}+ c a_{i - 2} (i \ ge2) a0 = 0, a1 = 1, ai = bai - 1 + cai - 2 (i ≥ 2), 지금 b 와 c 두 계수 의 값 을 드 리 겠 습 니 다. a n an. an 을 0 9 + 7 10 ^ 9 + 7 109 + 7 로 나 누 면 나머지 입 니 다.( 2 ≤ n ≤ 1 0 18 , 0 ≤ b , c ≤ 1 0 9 ) (2 \leq n \leq 10^{18}, 0 \leq b,c \leq 10^9) (2≤n≤1018,0≤b,c≤109)
예시 1
입력
2,1,1
출력
1
예시 2
입력
5,1,2
출력
11
아주 전형 적 인 행렬 의 빠 른 속도 입 니 다. 문 제 는 바 꾸 고 또 바 꾸 는 것 같 지만, 사실은 계수 행렬 의 위 치 를 바 꾸 면 됩 니 다. 계수 행렬 은 다음 과 같 습 니 다. [b c 1 0] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ c c0] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ rix} \ 오른쪽= \ \ left [\ \ begin {matrix} b & c \ \ \ 1 & 0 \ \ \ \ \ \ \ \ end {matrix} \ \ right] \ \ left [\ begin {matrix} a {i - 1} \ \ \ a {i - 2} \ \ \ \ \ \ \ \ end {matrix} \ \ right]
long long nthElement(long long n, long long b, long long c) {
long long a[2][2],ans[2][2],C[2][2],mod=1e9+7;
a[0][0]=b,a[0][1]=c;
a[1][0]=1,a[1][1]=0;
memset(ans,0,sizeof(ans));
for(int i=0;i<2;i++) ans[i][i]=1;
while(n>0)
{
if(n&1){
memset(C,0,sizeof(C));
for(int i=0;i<2;i++)
{
for(int k=0;k<2;k++)
{
if(a[i][k]==0) continue;
for(int j=0;j<2;j++)
{
C[i][j]=(C[i][j]+a[i][k]*ans[k][j])%mod;
}
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++)
ans[i][j]=C[i][j];
}
}
memset(C,0,sizeof(C));
for(int i=0;i<2;i++)
{
for(int k=0;k<2;k++)
{
if(a[i][k]==0) continue;
for(int j=0;j<2;j++)
{
C[i][j]=(C[i][j]+a[i][k]*a[k][j])%mod;
}
}
}
for(int i=0;i<2;i++){
for(int j=0;j<2;j++)
a[i][j]=C[i][j];
}
n>>=1;
}
return ans[1][0];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Numpy 퇴장? ! Sympy로 행렬을 편미분가필: 스칼라 함수를 벡터로 미분 안녕하세요, 노인 기술자입니다. 제 시대는 아직 끝나지 않습니다. 하지만 행렬 연산이라고 하면 Numpy라고 하는 시대는 끝난 것 같습니다. 그 이름도 Sympy (설마 신 py가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
