23648번 - Polynomial
계수가 {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개의 계수 모두 홀수이다.
댓글을 작성하려면 로그인해야 합니다.
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개의 계수 모두 홀수이다.