闲话
今日推歌：
帝国少女 - 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\) 的数量，则我们可以知道
第一个是所有可能减去不合法的可能，第二个是考虑有一段长度为 \(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\) 的）答案。由于原题是任意模数，常数可能大点。
标签：26,le,闲话,sum,times,ge,23.2,binom,Bob From： https://www.cnblogs.com/joke3579/p/chitchat230226.html