AtCoder Beginner Contest 246 F問題 typewriter

問題

提出解答

問題の概要

$\mathcal{A}$ を英小文字からなる集合 *1, $\mathcal{S} \subset \mathcal{A}$ に対して, $W_L(\mathcal{S})$ で $\mathcal{S}$ からなる長さ $L$ の文字列全体の集合とする. このとき,

$\displaystyle \mathcal{E}:=\bigcup_{i=1}^N W_L(\mathcal{S}_i)$

の濃度 (元の個数)を求めよ.

制約

$1 \leq N \leq 18$
$1 \leq L \leq 10^9$
$S_i \subset \mathcal{A}$

解法

以下の包除原理を利用する.

包除原理

$X$ を集合, $A_1, \dots, A_N$ を部分集合とする. このとき,

$\displaystyle \left|\bigcup_{i=1}^N A_i \right|=\sum_{\substack{J \subset [\![N]\!] \\ J \neq \emptyset} } (-1)^{|J|-1} \left|\bigcap_{j \in J} A_j \right|$

が成り立つ.

ここで, $\mathcal{S}, \mathcal{T} \subset \mathcal{A}$ に対して,

$|W_L(\mathcal{S})|=|\mathcal{S}|^L$
$W_L(\mathcal{S}) \cap W_L(\mathcal{T})=W_L(\mathcal{S} \cap \mathcal{T})$

である. よって,

$\displaystyle \begin{align} |\mathcal{E}| &=\left|\bigcup_{i=1}^N W_L(\mathcal{S}_j) \right| \\ &=\sum_{\substack{J \subset [\![N]\!] \\ J \neq \emptyset} } (-1)^{|J|-1} \left|\bigcap_{j \in J} W_L(\mathcal{S}_j) \right| \\ &=\sum_{\substack{J \subset [\![N]\!] \\ J \neq \emptyset} } (-1)^{|J|-1} \left| W_L \left(\bigcap_{j \in J} \mathcal{S}_j \right) \right| \\ &=\sum_{\substack{J \subset [\![N]\!] \\ J \neq \emptyset} } (-1)^{|J|-1} \left|\bigcap_{j \in J} \mathcal{S}_j\right|^L \\ \end{align}$

となる. $J \subset [\![N]\!], J \neq \emptyset$ となる $J$ は $2^N-1$ 個で全列挙可能であり, $\displaystyle \bigcap_{j \in J} \mathcal{S}_j$ についても $O(|J| |\mathcal{A}|)$ で計算可能である.

また, $|\mathcal{A}|=26$ であるから, $0^L, 1^L, \dots, 26^L$ を前計算で求めることにより, $|\mathcal{E}|$ を時間計算量 $O(2^N |J| |\mathcal{A}|+|\mathcal{A}| \log L)=O(|\mathcal{A}|(N2^N+ \log L))$ で計算できた.