점화식과 쿼리

시간 제한3초메모리 제한1024 MB

요약
초기 두 항과 n^k 항이 포함된 선형 점화식이 주어질 때, n이 10^18까지 커질 수 있는 최대 50000개의 질의에 대해 x_n을 100003으로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
수학, 동적 계획법, 정수론, 행렬
정답자
아직 제출이 없습니다

문제

수열 x_n\\{ x\_n \\}이 정수 n≥2n \ge 2에 대해 점화식 x_n=ax_n−1+bx_n−2+nkx\_n = ax\_{n-1} + bx\_{n-2} + n^k 를 만족한다. 수열 x_n \\{ x\_n \\}의 첫 두 항 x_0,x_1x\_0, x\_1과 점화식이 주어질 때, x_nx\_n을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 x_0,x_1,a,b,kx\_0, x\_1, a, b, k가 공백으로 구분되어 주어진다. (0≤x_0,x_1,a,b,k≤100,000)(0 \le x\_0, x\_1, a, b, k \le 100 \\, 000)

둘째 줄에 정수 QQ가 주어진다. (1≤Q≤50,000)(1 \le Q \le 50 \\, 000)

셋째 줄부터 QQ개의 줄에 걸쳐 한 줄에 하나씩, 정수 nn이 주어진다. (0≤n≤1018)(0 \le n \le 10^{18})

출력

한 줄에 하나씩, x_nx\_n을 소수 100,003100 \\, 003으로 나눈 나머지를 출력한다.

힌트

C/C++, Java 등의 언어에서 일부 변수를 3232비트 정수형으로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.

예제2

  1. 예제 1

    입력
    1 1 1 1 2
7
1
2
3
4
5
6
7
    예상 출력
    1
6
16
38
79
153
281

  2. 예제 2

    입력
    1 2 4 99999 300
1
10000007
    예상 출력
    77817