\(\sigma\) を文字集合のサイズとして (本問では \(\sigma = 26\))、\(\Theta(N 2 ^ \sigma + \sigma \log L)\) time で解く解法の解説です。なお、\(\sigma\) はワードサイズ以下であることを仮定します。

文字集合を \(\Sigma\) とします。各 \(A \subseteq \Sigma\) に対して、入力可能な長さ \(L\) の文字列 \(X\) であって、\(X\) に現れる文字の集合がちょうど \(A\) に一致するようなものの個数を \(f(A)\) とします。各 \(f(A)\) が求まれば、答えは \(\displaystyle \sum _ {A \subseteq \Sigma} f(A)\) として計算されます。

\(A\subseteq \Sigma\) を固定して、\(f(A)\) を計算することを考えます。まず、\(A\subseteq S _ i\) を満たすような \(i\) が存在しなければ \(f(A) = 0\) です。\(A \subseteq S _ i\) を満たす \(i\) が存在する場合は、\(f(A)\) は包除原理を用いて以下のように計算することが出来ます。式において \(B\) は、\(A\) には含まれるが長さ \(L\) の文字列には 必ず 含まれない文字の集合を表します。

\[ f(A) = \sum _ {B \subseteq A} (-1) ^ {|B|} |A \backslash B| ^ L \]

\(|B|\) の値ごとにまとめて計算することで、上記の和の計算を高速化することが出来ます。具体的には、次が従います。

\[ \sum _ {B \subseteq A} (-1) ^ {|B|} |A \backslash B| ^ L = \sum _ {i = 0} ^ {|A|} \binom{|A|}{i} \cdot (-1) ^ i \cdot (|A| - i) ^ L \]

累乗の前計算を \(\Theta(\sigma \log L)\) time、二項係数の前計算を \(\Theta(\sigma ^ 2)\) time で行っておけば、右辺の和を \(\Theta(\sigma)\) time で計算することができます。 さらに、右辺の和は \(|A|\) のみに依存するため、\(k = 0,\ldots, \sigma\) に対して次で表される \(g(k)\) を \(\Theta(\sigma ^ 2)\) time で前計算しておくことで、\(f(A)\) の計算を配列へのアクセスだけで済ませることが出来ます。

\[ g(k) = \sum _ {i = 0} ^ k \binom{k}{i} \cdot (-1) ^ i \cdot (k-i) ^ L \]

以上をまとめると、\(f(A)\) は式 \((1)\) で計算されます。\(\sigma\) がワードサイズ以下であることを仮定しているため、各 \(i\) に対して \(A \subseteq S _ i\) かどうかの判定は bit 演算を用いて定数時間で可能です。従って、各 \(f(A)\) は \(\Theta(N)\) time で計算できます。

\[ f(A) = \begin{cases} g(|A|) & \text{if}\; \exists i \;\text{s.t.}\; A\subseteq S _ i \\ 0 & \text{otherwise} \end{cases} \tag{1} \]

前計算にかかる時間計算量は \(\Theta(\sigma ^ 2 + \sigma \log L)\) であったので、本問を全体 \(\Theta(N \cdot 2 ^ \sigma + \sigma \log L)\) time で解くことが出来ました。

なお、\(A\subseteq S _ i\) を満たす \(i\) が存在するかどうかの判定に高速ゼータ変換を用いれば \(\Theta(N + \sigma \cdot 2 ^ \sigma + \sigma \log L)\) time で解くことも可能ですが、本問の制約下では先に紹介した解法の方が高速と思われます。

実装

C++ などの高速な言語でなければ本解法で AC を取ることは難しいかもしれません。

C++, 741 ms