No.2084 Mex Subset For All Sequences / No.1856 Mex Sum 2　高速解法

No.2084 Mex Subset For All Sequences / No.1856 Mex Sum 2 を統一的に解き、かつ計算量を落とす方法を紹介します。

問題リンク

問題概要

No.2084 の方の設定を採用します。(No.1856 も与えられた $M$ に $1$ を足せば同じ状況になります)
$0$ 以上 $M$ 未満の整数からなる長さ $N$ の整数列 $A$ すべてについて、すべての非空部分列の $\mathrm{mex}$ の和を考え、その和を $998244353$ で割った余りを求めてください。

解法

主客転倒と包除原理を用いて立式して、適当に変形します。
$\displaystyle \begin{aligned} &\sum_{k=1}^N \binom{N}{k} M^{N-k}\sum_{t=1}^{\min(N,M)} \sum_{l=0}^t \binom{t}{l} (-1)^l (M-l)^k \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \sum_{t=l}^{\min(N,M)} \binom{t}{l}-M^k\right) \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \sum_{t=0}^{\min(N,M)-l} \binom{t+l}{l}\right) - (2M)^N \\ =& \sum_{k=0}^N \binom{N}{k} M^{N-k} \left(\sum_{l=0}^{\min(N,M)} (-1)^l (M-l)^k \binom{\min(N,M)+1}{l+1}\right) - (2M)^N \\ =& \sum_{l=0}^{\min(N,M)} (-1)^l\binom{\min(N,M)+1}{l+1} \sum_{k=0}^N \left(\binom{N}{k} M^{N-k} (M-l)^k \right) - (2M)^N \\ =& \sum_{l=0}^{\min(N,M)} (-1)^l\binom{\min(N,M)+1}{l+1} (2M-l)^N - (2M)^N \\ \end{aligned}$

より、この問題を $O(\min(N,M)\log \min(N,M))$ で解くことができました。 No.2084 のような状況ならば、線形篩を用いれば時間計算量 $O(M + M\log N/\log M)$ になります。