부분집합 곱의 합 생성함수
다이아몬드 V의견: 0
\(N\)개의 보석이 있고, \(i\)번째 보석의 가치는 \(a_i\) 이다. 모든 계산은 소수 \(998{,}244{,}353\)으로 나눈 나머지로 한다.
각 \(k = 0, 1, \dots, N\)에 대해, 정확히 \(k\)개의 보석을 고르는 모든 방법에 대하여 고른 보석들의 가치의 곱을 모두 더한 값 \(e_k\) 를 구하여라. 즉
\(e_k = \displaystyle\sum_{\substack{S \subseteq \{1,\dots,N\} \\ |S| = k}} \ \prod_{i \in S} a_i\)
이는 다항식 \(\prod_{i=1}^{N} (1 + a_i x)\) 의 \(x^k\) 계수와 같다.
\(1 \le N \le 100{,}000\)
\(0 \le a_i \le 998{,}244{,}352\)
첫 줄에 보석의 수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 공백으로 구분되어 주어진다 (각각 \(0\) 이상 \(998{,}244{,}352\) 이하).
한 줄에 \(N+1\)개의 값 \(e_0, e_1, \dots, e_N\)을 공백으로 구분하여 출력한다.
3
2 3 5
1 10 31 30\(\prod(1+a_i x)=(1+2x)(1+3x)(1+5x)=1+10x+31x^2+30x^3\). \(e_0=1,\ e_1=2+3+5=10,\ e_2=2\cdot3+2\cdot5+3\cdot5=31,\ e_3=2\cdot3\cdot5=30\).
1
7
1 7보석이 하나뿐이라 \(1 + 7x\), 즉 \(e_0=1,\ e_1=7\).
riseoj 작성
출처 Original
평가 및 의견
부분집합 곱의 합 생성함수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
부분집합 곱의 합 생성함수