闲话

今日推歌：
帝国少女 - R Sound Design feat. 初音ミク
恋爱裁判 - 40mP feat. 初音ミク

杂题

今天打算刷一天杂题
所以随写随更新吧

好久没写了啊（

青鱼和区间

绝顶聪明的 Alice 和 Bob 在玩游戏。

Alice 选定一个 \([1, n]\) 内的整数 \(k\)，Bob 需要猜出这个数字。Bob 最开始会确定一个区间集合 \(S = \{[l_i, r_i] : 1\le l_i \le r_i\le n\}\)，他可以任意次地选择这其中的任意个区间，并同时询问 \(k\) 是否在这些区间中，Alice 会正确地同时回答。

给定 \(n\)。请计数集合 \(S\) 的数量，满足无论 \(k\) 是什么数字，Bob 都能通过恰当的操作（不加推导地）确定这个数字。答案对 \(998244353\) 取模。

\(n\le 10^5\)。

就是问有多少个集合 \(S\) 满足 \(\forall i \in [1, n],\ \exists T\subseteq S,\ \bigcap_{k\in T} k = \{i\}\)。
这题 lyin 昨天不让我在他那看题解
你先别急我急完了因而有了这个杂题

对于第 \(i\) 个数，记覆盖了 \(i\) 的区间集合为 \(S_i \subseteq S\)。构造一个长度为 \(n\) 的序列 \(\{a_i\}\)，满足 \(a_i = a_j\text{ iff } S_i = S_j\)。

可以发现，如果 \(a_i = a_j \text{ s.t. } i < j\)，则 \((i, j]\) 里的数定是无法被表示出来的。这证明显然，由于一个区间覆盖了 \(i\) 则覆盖了 \(j\)。我们可以从这里出发，考虑刻画不合法集合的性质。可以考虑这样的构造：
构造一个序列 \(b\)，初始为空。维护指针 \(i\)，初始在位置 \(1\)。每次将 \(a_i\) 放入 \(b\) 序列的末尾，取 \(\text{arg max}(a_j)\) 的 \(j\)，指针跳 \(i \leftarrow j + 1\)。举个例子：
\(a = [1, 9, 9, 8, 1, 0, 7, 2, 3, 5, 2, 3, 3]\)
\(b = [1, 0, 7, 2, 3]\)

这样我们就能通过 \(a\to b\) 来确定不合法的 \(a\) 了。
设 \(f(i)\) 是 \(n = i\) 时的答案，\(g(i, j)\) 是长度为 \(i\) 的 \(a\) 缩减到长度为 \(j\) 的 \(b\) 对应的 \(S\) 的数量，则我们可以知道

\[f(i) = 2^{\binom{i + 1}{2}} - \sum_{j = 1}^{i - 1} f(j) \times g(i, j)
\]

\[g(i, j) = g(i - 1, j - 1) + \sum_{k\ge 0} g(i - 1 - (k + 1), j - 1)\times 2^{\binom{k + 1}{2}}
\]

第一个是所有可能减去不合法的可能，第二个是考虑有一段长度为 \(k\ge 0\) 的区间被跳过的可能。

这就能做到 \(O(n^3)\)。但我们还可以走得更远。

观察第二个方程的形式。我们可以预见，这形式导出的是第一维的卷积，因此不妨对第一维求和。设

\[G_j(x) = \sum_{i\ge 0} g(i, j) x^i\quad A(x) = x + \sum_{k\ge 2} 2^{\binom{k - 1}{2}} x^k
\]

则我们能知道

\[\begin{aligned}
G_j(x) &= \sum_{i\ge 0} g(i, j) x^i
\\ &= \sum_{i\ge 0} g(i - 1, j - 1) x^i + \sum_{i\ge 0} \sum_{k\ge 0} g(i - 1 - (k + 1), j - 1)\times 2^{\binom{k + 1}{2}} x^i
\\ &= xG_{j - 1} + \sum_{k\ge 0} 2^{\binom{k + 1}{2}} \times \left( \sum_{i\ge 0} g(i - 2 - k, j - 1)x^i\right)
\\ &= xG_{j - 1} + \sum_{k\ge 0} 2^{\binom{k + 1}{2}} x^{k + 2} \times \left( \sum_{i\ge 0} g(i, j - 1)x^i\right)
\\ &= xG_{j - 1} + \sum_{k\ge 0} 2^{\binom{k - 1}{2}} x^{k} \times G_{j - 1}(x)
\\ &= G_{j - 1}(x) A(x)
\end{aligned} \]

即 \(G_{j}(x) = A(x)^j\)。

观察第一个方程的形式。设

\[F(x) = \sum_{i\ge 0} f(i) x^i\quad H(x) = \sum_{i\ge 0} 2^{\binom{i + 1}{2}} x^i
\]

则我们由这个半在线卷积的形式可以知道

\[\sum_{j = 1}^i f(j) g(i, j) = H[i]
\]

也就是

\[H[i] = \sum_{j = 1}^i f(j) [x^i] A(x)^j = [x^i] \sum_{j = 1}^i f(j) A(x)^j = [x^i] F(A(x))
\]

也就是 \(H(x) = F(A(x))\)。这启发我们使用拉格朗日反演解决问题。不难得到

\[\begin{aligned}

[x^n]F(x) = [x^n] H(A^{\langle -1\rangle}(x)) = \frac{1}{n} [x^{n - 1}] H'(x) \left( \frac{x}{A(x)}\right)^n

\end{aligned}\]

这形式的计算是简便的。因此可以在 \(O(n\log n)\) 的复杂度内得到（所有 \(1\le m\le n\) 的）答案。由于原题是任意模数，常数可能大点。