18168번 - Game with Polynomials 2 서브태스크

이 문제에서

• 편의상 0⁰: = 1로 둡니다.
• p = 998244353로 고정합니다. 이 수는 소수입니다.

키파는 이런 인터랙티브 문제를 내려고 했습니다.

다음과 같은 함수를 호출할 수 있습니다:

• evaluate(x): x를 다항식 Q(x)에 대입한 후 p로 나눈 나머지를 돌려줍니다.

evaluate 함수의 호출을 최대 q번 할 수 있습니다. 당신의 프로그램은 입력으로 n을 받아 Q(x)의 계수를 p로 나눈 나머지를 출력해야 합니다.

그런데, 테스트 케이스를 준비하면서 최대 q개의 수에 대해 차수가 n인 다항식을 평범하게 평가하는 것은 O(qn)이라는 것을 깨달았습니다! 작년처럼 편법을 쓰지 않으려고, 키파는 유능한 PSer인 캬륜하에게 어떻게든 이 문제의 빠른 인터랙터를 짜 달라고 부탁했습니다.

곤경에 처한 캬륜하는 여러분에게 도움을 청했습니다. 캬륜하 대신 인터랙터를 짜 줍시다!

첫째 줄에 n과 q가 주어집니다.

둘째 줄에 (n+1)개의 정수 a_n, a_n-1, …, a₁, a₀이 공백을 사이에 두고 주어집니다.

셋째 줄부터 q개의 줄에 걸쳐 정수 b₁, …, b_q가 주어집니다.

두 번째 줄부터 주어지는 모든 정수는 0 이상 p 미만입니다.

총 q개의 줄에 정수 하나씩을 출력합니다. i번째 줄에 출력하는 정수는

여야 합니다.

n ≤ 10³, q ≤ 10³.

n ≤ 2·10⁵, q ≤ 10⁵.