기초 수론 알고리즘 (8) 매트릭스 곱셈 법 과 선형 차례 추이 공식의 빠 른 값 구하 기

행렬 곱셈 은 zhx 흠 정 이 시험 가능성 이 매우 높다 고 말 한 것 이다!
행렬 곱셈
n * m 의 행렬 에 m * p 의 행렬 을 곱 하면 n * p 의 행렬 을 얻 을 수 있 습 니 다.따라서 구간 dp 템 플 릿 은 행렬 체인 곱셈 이 라 고 하지만 이것 은 중요 하지 않 습 니 다.행렬 곱셈 을 간단하게 말 하려 면 행 곱 하기 각 열 을 대응 하 는 줄 에 놓 는 것 이다.이렇게 말 하면 잘 모 르 겠 지만 나 는 코드 가 한 무더기 의 ∑ 보다 훨씬 뚜렷 하 다 고 생각한다.

void multi(int m,int n,int p){
    for(int i=0;ifor(int j=0;j
for(int k=0;k

특징 근 방정식
왜 특징 근 방정식 을 제기 합 니까?재미 있어 서 요.f (n) = af (n - 1) + bf (n - 2) 와 같은 전달 공식 에 대해 우 리 는 특징 근 방정식 으로 통 항 을 구 할 수 있다.참고 로 이런 방법 은 큰 문 제 를 쓸 때 사용 할 수 없 으 니 계 수 를 가만히 두 어 라.우선, 원 통 항 을 f (n) - af (n - 1) - bf (n - 2) = 0 의 형식 으로 쓴다.그 다음 에 하나의 방정식 을 풀 었 다. x2 - ax - b = 0, x1, x2 로 가정 하면 우 리 는 이 두 해 를 이 수열 의 특징 근 이 라 고 부른다.여기 서 주의해 야 할 것 은 실수 해 가 없다 면 이 수열 은 일반적으로 주기 적 인 것 이다.만약 x1 ≠ x2 라면 an = c1xn 1 + c2xn 2, 그 중에서 c1, c2 를 두 개의 수 를 가지 고 들 어가 면 알 수 있다.예 를 들 어 f (n) = 2f (n - 1) + 3f (n - 2), f (1) = 5, f (2) = 7 x2 − 2x − 3 = 0, x2 = − 1 ∴ f (n) = 3nc1 + (− 1) nc2 ∴ {3c1 − c2 = 59c1 + c2 = 7 해 의 c1 = 1, c2 = − 2 그러므로 f (n) = 3n − 2 (− 1)n, 요구 하면 빠 른 멱 을 가지 고 흐뭇 해 집 니 다. 그러나 문 제 는 있 습 니 다. 하 나 는 x1 = x2 의 경우 매우 번 거 롭 습 니 다. 하 나 는 우리 의 특징 근 이 무리수 이 고 많은 수의 모델 을 요구 하면 이런 방법 은 적용 되 지 않 습 니 다. 따라서 우 리 는 행렬 곱셈 법 으로 쓰 는 보편성 이 더욱 강 한 방법 을 제시 해 야 합 니 다.
행렬 곱셈 으로 최 적 화 된 선형 차례 추이 공식 으로 값 을 구하 다
우선 신기 한 것 을 보 자. 피 보 나치 수열 에 대해,
(fn,fn−1)⋅(1110)=(fn+1,fn)
이렇게 되면 우 리 는 상수 시간 내 에 이 통항 의 다음 항목 을 구 할 수 있다. 만약 n 항 을 요구한다 면 이 행렬 에 대해 멱 연산 을 하 는 것 과 같다.
무슨 생각 이 떠 오 르 지 않 았 습 니까? 맞습니다. 멱 을 보 자마자 빠 른 속도 로 멱 이 시작 되 었 습 니 다. 복잡 도 logn 은 선형 보다 어디 까지 높 았 는 지 모 릅 니 다.
그럼 더 홍보 할 수 있 을까요? 그럼요.
하면, 만약, 만약...
f(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k)
그렇다면 분명,
(fn,fn−1,...,fn−k+1,fn−k)⋅⎛⎝⎜⎜⎜⎜⎜⎜a1a2...ak−1ak10...0001...00...............00...0000...10⎞⎠⎟⎟⎟⎟⎟⎟=
(fn+1,fn,...,fn−k+2,fn−k+1)
너무 신기 하지 않 아 요? 이렇게 하면 행렬 로 빠 른 속도 로 달 릴 수 있어 요. 코드 를 놓 지 않 아 요.............................................