레야몬

1. 문제 랜덤 숫자 생성기(RNG)는 아래와 같은 선형 점화식으로 나타낼 수 있다. \(A_i = (A_{i-1} \times C_1 + A_{i-2} \times C_2 + \cdots + A_{i-k} \times C_k) mod 104857601\) N과 A1, A2, ..., Ak 그리고 C1, C2, ..., Ck가 주어졌을 때, AN을 구하는 프로그램을 작성하시오. 입력 -1- : \(k, N(1 \leq k \leq 30,000, 1 \leq N \leq 10^{18})\) -1- : \(A_i, C_i(0 \leq A_i, C_i < 104857601)\) 출력 -1- A_N 2. 재정의 X 3. 해결 방법 키타마사법에서 다항식의 곱과 나머지 연산을 NTT를 이용해 처리하면 된다. 자세한..