形式化题意
{(S1,S2,…,Sk)i=1⋃kSi=[n]}mod998244353
1≤n,k≤109
形式化思路
考虑重新刻画问题，设：
∀i∈[n],Ai={(S1,…,Sk)(∀j∈[k],Sj⊆[n])∧(∃j∈[k]:i∈Sj)}
那么要求的即：
i=1⋂nAimod998244353
以交集的角度并不方便计算，考虑容斥，已知全集的每个子集的补集的交集推出全体的交集，即：
i=1⋂nAi=J⊆[n]∑(−1)∣J∣j∈J⋂(Aj)c,
考虑此处
⋂j∈J(Aj)c 的意义：
不难发现以下命题成立：
(∀ℓ∈[k],Sℓ⊆[n]∖J)⟺((∀ℓ∈[k],Sℓ⊆[n])∧(∀j∈J,∀ℓ∈[k],j∈/Sℓ)).
因此有：
j∈J⋂(Aj)c=(2n−∣J∣)k=(2k)(n−∣J∣)
注意到一个子集的贡献只与该集合大小有关，因此有：
i=1⋂nAi=i=0∑n(in)(2k)n−i(−1)i
直接计算可获得 60 分；根据二项式定理可得：
i=0∑n(in)(2k)n−i(−1)i=(2k−1)n
用快速幂直接计算即可，时间复杂度为
Θ(logk+logn)，空间复杂度为
Θ(1)。