AtCoder Beginner Contest 241 Ex問題 Card Deck Score

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$1 \leq i \leq N$ に対して, $A_i$ と書かれたカードが $B_i$ 枚ある. このカードから $M$ 枚選んだとき, カードにかかれている整数の積をあり得る選び方全てにおいて考えた時の和を求めよ.

ただし, 同じ整数が書かれているカード同士は区別できないとする.

制約

$1 \leq N \leq 16$
$1 \leq M \leq 10^{18}$
$1 \leq A_i \lt 998244353$
$1 \leq B_i \leq 10^{17}$
$i \neq j \Rightarrow A_i \neq A_j$
$M \leq B_1+\dots+B_N$

解法

積和に関する問題なので, 形式的ベキ級数を用いて考えるとする.

$b$ 枚ある $a$ と書かれたカードから何枚か選ぶことに対応する $X$ を変数とする多項式 $P_{a,b}(X)$ は

$P_{a,b}(X)=1+a X+a^2 X^2+\dots+a^b X^b$

である. ここで, 等差数列の和の公式を利用することにより,

$P_{a,b}(X)=\dfrac{1-(a X)^{b+1}}{1-a X}$

となる.

このとき, 求めるべきは

$\displaystyle \left[X^M \right] \prod_{i=1}^N P_{A_i, B_i}(X)$

である.

ここで,

$\displaystyle\prod_{i=1}^N P_{A_i, B_i}(X)=\left(\prod_{i=1}^N \dfrac{1}{1-A_i X} \right) \prod_{i=1}^N \left(1-(A_i X)^{B_i+1} \right)$

である.

$\displaystyle Q(X):=\left(\prod_{i=1}^N \dfrac{1}{1-A_i X} \right)$ とする. 部分分数分解により,

$\displaystyle Q(X)=\sum_{i=1}^N \dfrac{C_i}{1-A_i X}$

となる有理数 $C_i \in \mathbb{Q}$ が存在する.

この $C_i$ を求めることを考える. 上の式に $\dfrac{1}{Q(X)}$ を掛けることにより, $Q(X)$ の定義から,

$\displaystyle 1=\sum_{i=1}^N C_i \left(\prod_{\substack{1 \leq j \leq N \\ j \neq i}} (1-A_j X)\right)$

となる. この式に $X=A_i^{-1}$ を代入することにより,

$\displaystyle 1=C_i \left(\prod_{\substack{1 \leq j \leq N \\ j \neq i}} (1-A_j A_i^{-1})\right) \quad \therefore C_i=\left(\prod_{\substack{1 \leq j \leq N \\ j \neq i}} (1-A_j A_i^{-1})\right)^{-1}$

となる.

また, $\displaystyle R(X):=\prod_{i=1}^N \left(1-(A_i X)^{B_i+1} \right)$ は愚直な展開を考えることにより, $2^N$ 以下の整数 $K$ と整数 $D_1, \dots, D_K, T_1, \dots, T_K$ が存在して,