题解：P8557 炼金术（Alchemy）
SkyWave
·
·
题解
形式化题意
给定 n, k，求出：
\left| \left\{ (S_1,S_2,\dots,S_k) \,\middle|\, \bigcup_{i=1}^{k} S_i = [n] \right\} \right| \bmod 998244353
1 \leq n, k \leq 10^9
形式化思路
考虑重新刻画问题，设：
\forall\, i \in [n],\quad A_i = \Bigl\{ (S_1,\dots,S_k) \,\Bigm|\, \bigl(\forall\, j\in [k],\; S_j \subseteq [n]\bigr) \land \bigl(\exists\, j\in [k] : \, i \in S_j\bigr) \Bigr\}
那么要求的即：
\left| \bigcap_{i=1}^{n} A_i \right| \bmod 998244353
以交集的角度并不方便计算，考虑容斥，已知全集的每个子集的补集的交集推出全体的交集，即：
\left|\bigcap_{i=1}^{n} A_i\right| = \sum_{J\subseteq [n]} (-1)^{|J|} \left|\bigcap_{j\in J} (A_j)^c\right|,
考虑此处 \bigcap_{j\in J} (A_j)^c 的意义：
\bigcap_{j\in J}(A_j)^c = \Bigl\{ (S_1,\dots,S_k) \,\Bigm|\, \left(\forall\, \ell \in [k],\; S_\ell \subseteq [n]\right) \land \left(\forall\, j \in J,\; \forall\, \ell \in [k],\; j \notin S_\ell\right) \Bigr\}.
不难发现以下命题成立：
\Bigl( \forall\, \ell \in [k],\; S_\ell \subseteq [n]\setminus J \Bigr)
\iff
\Bigl( \bigl(\forall\, \ell \in [k],\; S_\ell \subseteq [n]\bigr)
\land
\bigl(\forall\, j \in J,\; \forall\, \ell \in [k],\; j\notin S_\ell\bigr) \Bigr).
因此有：
\left|\bigcap_{j\in J}(A_j)^c\right| = \left(2^{n-|J|}\right)^k = ({2^k})^{\left( n-|J| \right)}
注意到一个子集的贡献只与该集合大小有关，因此有：
\left| \bigcap_{i=1}^{n} A_i \right| = \sum_{i=0}^{n} \binom{n}{i} (2^k)^{n-i} (-1)^i
直接计算可获得 60 分；根据二项式定理可得：
\sum_{i=0}^{n} \binom{n}{i} (2^k)^{n-i} (-1)^i = (2^k-1)^n
用快速幂直接计算即可，时间复杂度为 \Theta(\log k + \log n)，空间复杂度为 \Theta(1)。