[ABC241 Ex] Card Deck Score

https://atcoder.jp/contests/abc259/tasks/abc259_h

kenkoooo 레이팅: 2881

체감 난이도: D3 (근데 이 정도 난이도의 수학 문제는 풀어본 적이 없어서 잘 모르겠다.)

Tag: Math, Bitmask

---

$N$ 종류의 카드가 있다. $i$번 종류의 카드는 $A_i$가 쓰여 있고, 총 $B_i$장이 있다.

$M$개의 카드를 고른 뒤, 그 카드에 있는 수를 모두 곱한 값을 $S$라고 하자. 카드를 고르는 모든 경우에서의 $S$ 합을 $998\ 244\ 353$으로 나눈 나머지를 출력하는 문제이다. $N$이 $16$ 정도로 작다는 점을 유념하자.

---

에디토리얼의 도움을 받았다. 아래 내용은 수학적으로 아마 엄밀하지는 않을 거고, 이해한 풀이의 흐름을 기반으로 서술되어 있다.

 

수 범위가 무지하게 큰데, 겁먹지 말고 가능한 모든 경우의 수를 다항식으로 표현하는 것으로 시작한다. 구하고자 하는 답은 아래 다항식 $f(x)$의 $M$차 항의 계수이다.

$$ f(x) = \prod_{i=1}^{N}{ \sum_{j=0}^{B_i} {{A_ix}^j} } $$

여기서 등비수열 합의 곱 형태로 나타내어진 부분을 변형한다.

$$ f(x) = \prod_{i=1}^{N}{ \frac{1 - {A_ix}^{B_i + 1}} {1 - A_ix} } $$

이제 분모에 해당하는 다항식을 아래와 같이 여러 부분분수의 합으로 분해한다.

$$ \prod_{i=1}^{N}{\frac{1}{1 - A_ix}} = \sum_{i=1}^{N} {\frac{c_i}{1-A_ix}} $$

 

이제 $c_i$를 찾는다. 일단 양변에 $\prod_{i=1}^{N}{1 - A_ix}$ 를 곱해보자.

$$1 = \sum_{i=1}^{N} c_i{\prod_{j=1 \\ j \neq i}^{N}{ (1 - A_jx)} } $$

여기서 모든 $c_i$는 주어진 조건에 따라 $\bmod$ 범위 내에서 유일하게 존재한다. 존재성에 대한 엄밀한 증명은 잘 이해하지 못했으나, 대충 $N-1$차 다항식이 $x$값이 다른 $N$개의 서로 다른 점을 지난다는 사실에서 유도되는 것 같다.

운이 좋게도 나머지 항들을 잘 소거해서 $c_i$를 쉽게 구할 수 있다. 주어진 다항식의 $x$에 $A_i ^ {-1}$을 대입하면, 아래와 같이 식이 정리되고, $c_i$를 모듈러 역원을 이용해 구할 수 있게 된다.

$$ 1 \equiv c_i{\prod_{j=1 \\ j \neq i}^{N}{ (1 - A_jA_i^{-1})} } \bmod 998\ 244\ 353$$

 

이제 $f(x)$의 $M$차항의 계수를 계산한다. $f(x)$를 다시 한번 정리해 보면 아래와 같다.

 

$$ f(x) = \sum_{i=1}^{N} {c_i \left[ ( \sum_{j=0}^{B_i} {{A_ix}^j} ) ( \prod_{j=1 \\ j \neq i}^{N}{ (1 - {A_ix}^{B_i + 1} )} ) \right] } $$

 

$ \prod_{j=1 \\ j \neq i}^{N}{ (1 - {A_ix}^{B_i + 1})} $ 에 해당하는 다항식의 항 개수가 $O(2^N)$개라는 점을 이용해서 답을 구할 수 있다. 이 부분의 항의 계수가 결정이 되면, 자동적으로 $ \sum_{j=0}^{B_i} {{A_ix}^j} $에 해당하는 부분의 항 계수도 결정이 된다. 따라서 앞 다항식의 모든 항에 대해, 계수를 잘 계산하면 전체 문제를 $O(N2^N logM)$ 시간에 해결할 수 있다. 

 

https://atcoder.jp/contests/abc241/submissions/47561254