레야몬

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