mod = 10**8+7
def multiply(A,B):
S = [[0]*K for i in range(K)]
for i in range(K):
for j in range(K):
for k in range(K):
S[i][j] += A[i][k]*B[k][j]
S[i][j] %= mod
return S
def cal(A,n):
if n==1:
return A
c = cal(A,n//2); c2 = multiply(c,c)
return multiply(c2,A) if n%2 else c2
for _ in range(int(input())):
K,N = map(int,input().split()); K += 1
matrix = [[0]*K for i in range(K)]
matrix[0][0] += 1; matrix[0][-1] += 1
for i in range(K-1):
matrix[i+1][i] = 1
print(cal(matrix,N)[0][0])
간단한 행렬 거듭제곱 문제
피보나치 수 문제를 푸는것과 비슷한 원리로 풀면 된다.
병아리가 알을 낳으면 K일 후에 부화한다. 즉, 오늘 낳은 알은 K+1일 뒤에 부화한다.
이를 통해 "N일의 병아리 수 = N-1일의 병아리 수 + N-1-K일의 병아리 수" 라는 점화식이 성립함을 알 수 있다.
점화식을 구했으니, 이제 할일은 피보나치 수열을 풀때처럼 행렬을 구하고 행렬을 N번 거듭제곱 해주는 것 뿐이다.
참고로 이 문제는 mod가 10^9+7이 아닌 10^8+7이다.... 나뿐만 아니라 많은 사람들이 이거때문에 낚인것 같다.