闲话
？？？？这luogu编译器怎么回事
在本地和 at 上都能过编，在luogu上就过不了？
xdm有遇到过这种事情的吗
推歌：朝死暮生 by 北山薇 et al. feat. 洛天依AI
补题
对一棵 \(2n + 1\) 个点的有标号树，称它是好的，当且仅当树上每个点具有一个 \(\{0, 1, 2\}\) 中的权值，其中恰有 \(1\) 个权值为 \(2\) 的点，\(n\) 个权值为 \(0,1\) 的点，并使得不存在一条边的两个端点权值相同。
给定 \(n\)，对不同的 \(\text{typ}\)，您需要回答不同的问题：
\(\text{typ} = 0\)：计数 \(2n + 1\) 个点的好树。
\(\text{typ} = 1\)：对每棵好树，我们需要在删除权值为 \(2\) 的点以及对应边后，在每个极大联通子树内选择恰好一个点做标记。计数做标记的可能方案。
这个题还算好 specify 的，所以写一下（
题面经过转化了。首先因为权值为 \(2\) 的点只有一个，我们可以将它视为树根，并将连在它上面的点视作对应子树的根。这样子问题（一棵极大联通子树）就变为有标号有根树了，而这是较为简单的。称一棵有标号有根树是好的，当且仅当树上每个点具有一个 \(\{0, 1\}\) 中的权值，并使得不存在一条边的两个端点权值相同。令 \([x^ny^m/n!m!]F_k(x, y)\) 计数根的权值为 \(k\)，由 \(n\) 个权值为 \(0\) 的点、\(m\) 个权值为 \(1\) 的点组成的有标号有根树。那么根据有标号 \(\text{Set}\) 构造的生成函数翻译，自然有
\[\left\{\begin{aligned} F_0 = x\exp F_1 \\ F_1 = y\exp F_0 \end{aligned}\right.\]但这题怎么会让你这么轻易完成 analyse 呢？让我们先看看 \(\text{typ} = 1\)……
我们首先考察可以作为权值为 \(2\) 的点的子树的组合类对应的 egf，容易知道这就是 \(F_0 + F_1\)。那么仍然是无顺序排列，我们知道答案就是
\[\left[\frac{x^ny^n}{n!n!}\right] \exp (F_0 + F_1) \]还挺简单的！就是公式的排版有点难看（
施二元拉格朗日反演知道这就是
\[\begin{aligned} & \left[\frac{x^ny^n}{n!n!}\right] e^{x + y} e^{nx} e^{ny} \left\lvert \begin{matrix} 1 & -x \\ - y & 1 \end{matrix} \right\rvert \\ = \ &\left[\frac{x^ny^n}{n!n!}\right] e^{(n + 1)(x + y)}(1-xy) \end{aligned}\]可以贡献出 \(x^i y^j\) 项的只可能是 \((x + y)^{i + j}\)。所以知道
\[[x^my^m] e^{(n + 1)(x + y)} = [x^my^m] (n + 1)^{2m} \dfrac{(x + y)^{2m}}{(2m)!} = \binom{2m}{m}\dfrac{(n + 1)^{2m}}{(2m)!} \]因此原式
\[\begin{aligned} \\ = \ & (n!)^2 \left(\binom{2n}{n} \frac{(n + 1)^{2n}}{(2n)!} - \binom{2n - 2}{n - 1} \frac{(n + 1)^{2n - 2}}{(2n - 2)!}\right) \\ = \ & (n + 1)^{2n} - n^2(n + 1)^{2n - 2} \\ = \ & (n + 1)^{2n - 2}(2n + 1) \end{aligned}\]可以 \(O(\log n)\)。还挺简单的！
但这题怎么会让你这么轻易完成 analyse 呢？让我们再看看 \(\text{typ} = 1\)……
这是什么？我们还是需要每个子树的组合类对应的 egf \(F_0 + F_1\)，但这次，这个函数里每个 \(x^ny^m\) 项的贡献要乘以 \(n + m\)。也就是，我们需要实现一个算子，使得 \(x^ny^m \rightarrow (n + m)x^ny^m\)，自然想到了求导。因此我们只需要设计 \(x\dfrac{\partial}{\partial x} + y\dfrac{\partial}{\partial y}\)，就可以分别取得两个占位元的指数了。因此记 \(\dfrac{\partial}{\partial x}\) 为 \(\partial_x\)，我们知道答案就是
\[\left[\frac{x^ny^n}{n!n!}\right] e^{(x\partial_x + y\partial_y)(F_0 + F_1)} \]受 \(\text{typ} = 0\) 的启发，我们仍然希望使用多元拉格朗日反演来击破复合的形式。然而目前的结构有求导，无法立即使用拉反。因此我们需要找到 \(\partial F_k \to F_0, F_1\) 的具体关系。首先对方程组对 \(x\) 求偏导，得到
\[\partial_x F_0 = e^{F_1} + x \left(\partial_x F_1\right)e^{F1} = e^{F_1} + \left(\partial_x F_1\right) F_0 \]\[\partial_x F_1 = y (\partial_y F_0) e^{F_0} = F_1 (\partial_y F_0) \]得到
\[x\partial_x (F_0 + F_1) = \frac{F_0(1 + F_1)}{1 - F_0 F_1} \]真行啊这？这其实引发了我的一个疑问，我们能在多严格的限制条件下保证存在这样一个关系，或者断言它不存在？这问题暂且搁置，目前的处理方法还比较依赖某些看似独立的性质。
对 \(y\) 求偏导得到了相同的结构，我们需要计算的就是
\[\left[\frac{x^ny^n}{n!n!}\right] \exp \left( \frac{F_0 + F_1 + F_0F_1}{1 - F_0F_1}\right) \]现在就能做拉反了。拉反完得到
\[\begin{aligned} \\ = \ & \left[\frac{x^ny^n}{n!n!}\right] \exp \left( \frac{x + y + 2xy}{1 - xy}\right) e^{n(x + y)} (1 - xy) \end{aligned}\]现在要考虑减元了。减元的进行，大多时候要么是直接找到一个元的系数，要么是换元后找到一个元的系数。注意到这式子是关于 \(x, y\) 完全对称的，这也会让我们找到系数的难度增加——因为提取哪个元完全是一样的。那么我们不妨通过换元，直接破坏掉这一性质。
启发我们的是我们要提取的系数，我们如果做换元 \(u = xy, v = y\)，那么要提取的就是 \(u^nv^0\) 次项。这应当会大大简化减元的过程。我们目前的目标是确定形式 laurent 级数（占位元为 \(v\)）的常数项。于是有
\[\begin{aligned} \\ = \ & \left[\frac{u^nv^0}{n!n!}\right] \exp \left( \frac{u/v + v + 2u}{1 - u}\right) e^{n(u/v + v)} (1 - u) \\ = \ & (n!)^2\left[u^nv^0\right] (1 - u) \exp \left( \frac{u/v + v + 2u}{1 - u} + n(u/v + v)\right) \\ = \ & (n!)^2\left[u^nv^0\right] (1 - u) \exp \left\{(u/v + v)\left(\frac{1}{1-u} + n\right) + \frac{2u}{1-u}\right\} \\ = \ & (n!)^2\left[u^nv^0\right] (1 - u) \exp \left(\frac{2u}{1-u}\right) \sum_{i\ge 0} \left(n + (1 - u)^{-1}\right)^i \frac{(u/v + v)^i}{i!} \end{aligned}\]这里考虑最后一个求和都枚举了些什么。我们需要的是 \([v^0](u/v + v)^i\)，这也就要求了 \(i = 2k\)，这样就有
\[[v^0](u/v + v)^i = [v^0](u/v + v)^{2k} = \binom{2k}{k} u^k \]得到
\[\begin{aligned} \\ = \ & (n!)^2\left[u^n\right] (1 - u) \exp \left(\frac{2u}{1-u}\right) \sum_{k\ge 0} \left(n + (1 - u)^{-1}\right)^{2k} \frac{1}{(2k)!} \binom{2k}{k} u^k \\ = \ & (n!)^2\left[u^n\right] (1 - u) \exp \left(\frac{2u}{1-u}\right) \sum_{k\ge 0} \frac{\left(n + (1 - u)^{-1}\right)^{2k}}{(k!)^2} u^k \\ = \ & (n!)^2\left[u^n\right] (1 - u) \exp \left(\frac{2u}{1-u}\right) {}_1F_2 \left( \left.\begin{matrix} 1\\1, 1 \end{matrix}\right\rvert \frac{u\left(n(1-u) + 1\right)^{2}}{(1-u)^2}\right) \end{aligned}\]可以 \(O(\sqrt n \log n)\)，这是一个 29 阶整式递推（如果我没记错的话）。
不是？为啥我同一份代码开同样的编译选项，在P1001能过编，在P10324过不了编啊？？？？？？？
问题很可能出现在 ode_pFq(const vector
算了，就当我过了吧。
code
signed main() {
int typ, n;
cin >> n >> typ;
if (typ == 0) {
cout << 1ll * qp(n + 1, 2 * n - 2) * (2 * n - 1) % mod;
} else {
pfrac A;
A.x = { Z(n + 1), Z(mod - n) };
A.x = A.x * A.x * topoly("x"_p);
A.y = { Z(1), Z(mod - 1) };
A.y = A.y * A.y;
ODE ans = ode_power(1).composite(topoly("1 - x"_p)) *
ODE_EXP.composite(pfrac(topoly("2x"_p), topoly("1 - x"_p))) *
ode_pFq({}, {1}).composite(A);
cout << 1ll * p_recur(n, ans.recur(min(40, n), {1, "x^2 + 2x + 2"_p.eval(n), ("x^4 + 4x^3 + 10x^2 + 20x + 21"_p * gifc(2) * gifc(2)).eval(n)}), ans.trans_poly()) * gfac(n) % mod * gfac(n) % mod << endl;
}
}