[백준] 22964. conv1d

https://www.acmicpc.net/problem/22964

요약

• 길이 n인 배열에 길이 k인 필터를 씌워서 합성곱(?) 연산을 시킴
• 배열에 가능한 숫자는 1 ~ X 범위
• 모든 경우의 수를 고려했을 때 나올 수 있는 결과들의 합을 나열

접근법

• a 배열의 첫자리, b 배열의 첫자리만 일단 고려해봄
• 1 * 1로 해서 결과 배열의 첫자리에 갈 수 있음
• 이렇게 되는 경우의 수는 나머지 자리들이 채워지는 경우의 수 = ${X^{n + k - 2}}$ 개임
• 1 * 2도 마찬가지
• 순서쌍으로 생각하면 (1, 1), (1, 2) ... (1, n), (2, 1), ...(n, n)
• 식을 정리하면 ${sum(1, n) * sum(1, n) * X^{n + k - 2}}$
• 들어갈 수 있는 자리는 1 ~ k자리 : ${sum(1, n) * sum(1, n) * X^{n + k - 2} * k}$
• 다른 자리들도 마찬가지 일 것임