闲话
明天就过年了！
明天很可能没有闲话 那就在这里祝每个我闲话的读者新年快乐吧！
新年一定要快乐啊！首先得快乐才能想接下来的事呢！
中午打了打《德军总部·新秩序》
深感现在没有心力去打硬核射击游戏了（
当然如果你给我一个呼吸回血我还是能打的（
没啥可写的哦（
啊我还要封装板子 就写到这吧
求斯特林数
第二类斯特林数 \(\begin{Bmatrix} n \\m \end{Bmatrix}\) 表示把 \(n\) 个不同元素划分成 \(m\) 个相同的集合中（不能有空集）的方案数。
给定\(n\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{Bmatrix} n \\i \end{Bmatrix}\)。对 \(167772161\) 取模的值。
\(1\le n \le 2^{18}\)。
熟知
\[m^n = \sum_{i = 0}^m \binom{m}{i} \begin{Bmatrix} n \\i \end{Bmatrix} i! \]可以组合意义得到这个公式。左侧就是 \(n\) 个元素随意放入 \(m\) 个有标号集合中，可以存在空集的种类数。然后我们首先枚举 \(i\) 个有标号集合，直接对选出的这些可视为无标号的集合计算方案数得到右侧。
作二项式反演得到
\[\begin{Bmatrix} n \\m \end{Bmatrix} m! = \sum_{i = 0}^m (-1)^{m - i} \binom{m}{i} i^n \]拆开组合数后得到
\[\begin{Bmatrix} n \\m \end{Bmatrix} = \sum_{i = 0}^m \frac{(-1)^{m - i}}{(m - i)!} \frac{i^n}{i!} \]这是标准的卷积形式。直接做一次卷积即可，复杂度为 \(O(\text M(n))\)。
给定 \(n,k\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{Bmatrix} i \\k \end{Bmatrix}\) 对 \(167772161\) 取模的值。
\(1\le n, k < 2^{17}\)。
考虑集合数量是相同的，所以可以对每个集合构造生成函数，然后求 \(k\) 次幂即可。
考虑相同的集合不好作组合意义，我们转换成不同的集合，然后构造 egf 组合，最后答案除以 \(k!\) 即可。
对单个盒子，我们构造 egf 为
\[F(x) = \sum_{i \ge 1} \frac{x^i}{i!} = e^x - 1 \]然后可以写出
\[\begin{Bmatrix} n \\k \end{Bmatrix} = \frac{1}{k!}[x^n/n!](e^x - 1)^k \]直接计算即可。复杂度为 \(O(\text M(n))\) 或分治 FFT。
第一类斯特林数 \(\begin{bmatrix}n\\ m\end{bmatrix}\) 表示将 \(n\) 个不同元素构成 \(m\) 个圆排列的数目。
给定 \(n\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{bmatrix}n\\ i\end{bmatrix}\) 对 \(167772161\) 取模的值。
\(1\le n < 2^{18}\)。
熟知
\[x^{\overline{n}} \sum_{i = 0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i \]证明可以考虑归纳法。
对于求幂相关的构造，一般是寻找共性后分治求解。在本题中我们可以发现
\[x^{\overline{2n}} = x^{\overline{n}} (x + n)^{\overline{n}} \]不妨考虑从 \(x^{\overline{n / 2}}\to x^{\overline{n}}\) 的倍增过程，过程中适当地乘入 \((x + n)\) 即可。设 \(f(n) = x^{\overline{n}}\)，我们需要的就是从 \(f(x)\) 得到 \(f(x + n)\)，容易发现这是个点值平移的过程。
可以发现
\[\begin{aligned} f(x + k) &= \sum_{i = 0}^n f[i](x + k)^i \\ &= \sum_{i = 0}^n f[i]\sum_{j = 0}^i \binom{i}{j} x^j k^{i - j} \\ &= \sum_{j = 0}^n \left(\sum_{i = j}^n \frac{f[i]}{i!} \times \frac{k^{i - j}}{(i - j)!}\right) \frac{x^j}{j!} \\ &= \sum_{j = 0}^n \left(\sum_{i = 0}^{n - j} \frac{f[i + j]}{(i + j)!} \times \frac{k^{i}}{i!}\right) \frac{x^j}{j!} \end{aligned}\]这内部是一次卷积可以解决的问题，我们直接设 \(G[i] = F[n - i] / (n - i)!\) 后代替原式中的这部分即可。因此可以 \(O(\text M(n))\) 地解决点值平移的问题。
应用回原问题后只需要再做一次乘法，总时间复杂度 \(T(n) = T(n / 2) + O(\text M(n)) = O(\text M(n))\)。
给定 \(n,k\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{bmatrix}i\\ k\end{bmatrix}\) 对 \(167772161\) 取模的值。
\(1\le n, k < 2^{17}\)。
考虑集合数量是相同的，所以可以对每个集合构造生成函数，然后求 \(k\) 次幂即可。
考虑相同的集合不好作组合意义，我们转换成不同的集合，然后构造 egf 组合，最后答案除以 \(k!\) 即可。
对于一个环的情况可以直接对 \(\begin{bmatrix}n\\ 1\end{bmatrix}\) 构造生成函数，也就是
\[F(x) = \sum_{n \ge 0} \begin{bmatrix}n\\ 1\end{bmatrix} \frac{x^n}{n!} = \sum_{n \ge 0} \frac{x^n}{n} = \ln \frac{1}{1 - x} \]最后一步见此。
然后自然可以写出
\[\begin{bmatrix}n\\ k\end{bmatrix} = \frac{1}{k!}\left[\frac{x^n}{n!}\right]\left(\ln \frac{1}{1 - x}\right)^k \]直接实现即可，总时间复杂度为 \(O(\text M(n))\)。
回头会封装一个实现扔在板子里。
标签：bmatrix,begin,end,Bmatrix,闲话,sum,20,23.1,frac From： https://www.cnblogs.com/joke3579/p/chitchat230120.html