J - Set Sequence Editorial by Rogi

公式解説と同様に，\(F = \displaystyle\prod_{i=1}^{N}(1+x_i)\) とおきます．

\(|T| = K\) を固定して考えることで，答えは次に等しいです．

\[ \left[x_1^{A_1} \cdots x_N^{A_N}\right] \sum_{K=1}^{\infty} (F-1)^K \]

式変形すると，最終的に次の値を求めることになります．

\[ \sum_{n=0}^{P-1} 2^{-n} \prod_{i=1}^{N} \binom{n}{A_i} \]

式変形 $$ \sum_{K=1}^{\infty} (F-1)^K = \frac{1}{2-F} - 1 $$ 末尾の $-1$ は無視します． 以下では $\mathbb{F}_P[x_1, \dots, x_N] / (x_1^P, \dots, x_N^P)$ 上で考えます． $$ 2^P - F^P = (2-F) \sum_{n=0}^{P-1} 2^{P-1-n} F^n $$ が成り立ちますが，
  • $2^P = 2$
  • $\displaystyle F^P = \prod_{i=1}^{N} (1+x_i)^P = \prod_{i=1}^{N}(1+x_i^P) = 1$
  • $2^{P-1-n} = 2^{-n}$
をそれぞれ代入して次を得ます． $$ \frac{1}{2-F} = \sum_{n=0}^{P-1} 2^{-n} F^n $$ $\displaystyle\left[x_1^{A_1} \cdots x_N^{A_N}\right] F^n = \prod_{i=1}^{N} \binom{n}{A_i}$ より，求める値は次のように書けます． $$ \sum_{n=0}^{P-1} 2^{-n} \prod_{i=1}^{N} \binom{n}{A_i} $$


\(\displaystyle\prod_{i=1}^{N}\binom{n}{A_i} = \frac{(n!)^N}{\prod A_i! \prod (n-A_i)!}\) より， \(n = \max(A), \dots, (P-1)\) について \(\displaystyle\prod_{i=1}^{N}(n-A_i)!\) が列挙できれば良いです．

原始根をとり，離散対数を \(\operatorname{ind}(\cdot)\) とします．

\[ \operatorname{ind}\left(\prod_{i=1}^{N}(n-A_i)!\right) = \sum_{i=1}^{N} \operatorname{ind}\bigl((n-A_i)!\bigr) = \sum_{x = 1}^{n} C_x \cdot \operatorname{ind}\bigl((n-x)!\bigr) \]

ここで \(C_x\) は \(A\) に含まれる \(x\) の個数です．

これは \(C_x\) と \(\operatorname{ind}(x!)\) の畳み込みの形です．例えば atcoder::convolution_ll を用いて \(O(P\log P)\) 時間で計算できます．

全体で \(O(N + P\log P)\) 時間です．

posted:
last update: