nnaxh0   1년 전

문제

계수가 {0, 1}인 다항식 P가 주어졌을 때, P를 n제곱했을 때 홀수인 계수의 개수를 출력한다.

입력

첫 번째 줄에 다항식의 차수 d (1 ≤ d ≤ 20)가 주어진다.

두 번째 줄에 d+1개의 정수 ai (ai ∈ {0, 1})가 낮은 차수부터 오름차로 주어진다.

세 번째 줄에 정수 n (1 ≤ n ≤ 1016)이 주어진다.

출력

홀수인 계수의 개수를 한 줄에 출력한다.

노트

1번 예제에서 P(x)3=1+3x+3x2+x3이고, 4개의 계수 모두 홀수이다.

댓글을 작성하려면 로그인해야 합니다.