闲话

发现自己没学过欧拉数相关的推导
~~开 koishi 的排列去（~~
upd：实在想不出 EI 给出的 -x/(1-x) + 1/(1-x) 的形式
只能推出两个\sum 的形式所以摆了
how EI's mind works?
upd 2.18：看懂了 HEMW？

今日放了 be 的歌？
不谈演唱中只有少部分人能接受的部分
其实失真的人声还是比较自然的感觉术力口在表达方式上也有类似的元素
副歌的编曲还行吧我感觉和演唱的表现不是很搭
当然如果这是刻意为之的当我没说吧（

今日推歌：我的悲伤是水做的 - chilichill feat. 洛天依

欧拉数 \(\text{BGF}\) 推导

考虑一个形式：

\[\frac{1}{n!}\sum_{m} \left\langle \begin{matrix}{n} \\ {m}\end{matrix}\right\rangle \binom{m}{n - i} = i! \begin{Bmatrix} n \\ i \end{Bmatrix}
\]

这可以通过组合意义说明。左侧就是计数长为 \(n\) 的钦定了 \(n - i\) 次上升的排列，这使得原排列被分割为 \(i\) 个有序的下降段。这也就是 \(n\) 个不同的球放入 \(i\) 个不同的集合内的方案数，即右侧。这也说明左侧的 gf 即为 \([x^n] (e^x - 1)^i\)。

设

\[F(x, t) = \sum_{n\ge 0}\sum_{m\ge 0} \left\langle \begin{matrix}{n} \\ {m}\end{matrix}\right\rangle \frac{x^n}{n!} t^m
\]

我们可以配凑如上的形式。具体地，考察如下的代入：

\[\begin{aligned}

&F(xt, 1 + t^{-1})
\\ = \ & \sum_{n\ge 0}\sum_{m\ge 0} \left\langle \begin{matrix}{n} \\ {m}\end{matrix}\right\rangle \frac{x^n}{n!}t^n \left(1 + t^{-1}\right)^m
\\ = \ & \sum_{n\ge 0}\sum_{m\ge 0} \sum_{i \ge 0} \left\langle \begin{matrix}{n} \\ {m}\end{matrix}\right\rangle \binom{m}{i} \frac{x^n}{n!}t^{n - i}
\\ = \ & \sum_{n\ge 0}\sum_{i \ge 0} \left(\frac{1}{n!} \sum_{m} \left\langle \begin{matrix}{n} \\ {m}\end{matrix}\right\rangle \binom{m}{n - i} \right) x^n t^i
\\ = \ & \sum_{n\ge 0}\sum_{i \ge 0} i! \begin{Bmatrix}{n} \\ {i}\end{Bmatrix} x^n t^i
\\ = \ & \sum_{i\ge 0}(e^x - 1)^i t^i
\\ = \ & \left(1 - t\left(e^x - 1\right)\right)^{-1}

\end{aligned}\]

这样我们即可得到

\[F(x, t) = \left(1 - (t - 1)^{-1}\left(e^{x(t - 1)} - 1\right)\right)^{-1} = \frac{t - 1}{t - e^{x(t - 1)}}
\]

模拟赛 T3

我们改写原式为 \(A(B - I) = 0\)，并记 \(M = B - I\)。考察非平凡的 \(M\) 后容易发现，假设 \(\text{rank}(M) = k\)，则对应的 \(A\) 有 \(p^{(n - k)m}\) 种取法，因 \(M\) 有 \(n - k\) 行被其他维表出，乘后定为 \(0\)，则这些行对应 \(A\) 上 \(n - k\) 列取值随意。

因此现在的问题就是对 \(k\) 计数 \(M \text{ s.t. } \text{rank}(M) = k\)。考虑将其拆分。
由经典结论可以知道，一个 \(\mathbb F_p^n\) 内空间的 \(k\) 维子空间数是 \(\begin{bmatrix} n \\ k\end{bmatrix}_p\)，即 \(\text{q-binomial}\)。我们首先选出一个 \(k\) 维子空间，以及它的一组基 \(\langle b_k\rangle\)。构造矩阵 \(B = [b_1 \ b_2 \ \cdots \ b_k]\)，这是一个 \(n\times k\) 的满秩矩阵。
可以发现，\(M\) 一定形如 \(B\times C\)，其中 \(C\) 为一个 \(k\times n\) 的满秩矩阵，且不同的 \(C\) 对应不同的 \(M\)。我的理解是，考虑矩阵是线性变换，\(B\) 对应一个 \(\mathbb F_p^n\to \mathbb F_p^k\) 的满射，\(C\) 对应一个 \(\mathbb F_p^k\to \mathbb F_p^n\) 的单射，而两者的乘法对应映射的复合，因此得到了一个 \(\mathbb F_p^n\to \mathbb F_p^n\) 但只保留了 \(k\) 维彼此独立信息的映射。因此最后 \(M\) 两两不同且 \(\text{rank}(M) = k\)。由经典结论可以知道，\(C\) 的数量为 \(\prod_{i = 0}^{k - 1}(p^n - p^i)\)。
因此对 \(k\) 的答案即为