395. CF717A Festival Organization & P5320 [BJOI2019] 勘破神机
396. square869120Contest #3 G Sum of Fibonacci Sequence
特判 \(n = 1\)。将 \(n, m\) 都减 \(1\)，答案即为
\[[x^m]\frac{1}{(1 - x - x^2)(1 - x)^n} \]若能把这个分式拆成 \(\frac{A(x)}{(1 - x)^n} + \frac{B(x)}{1 - x - x^2}\) 的形式，其中 \(\deg A(x) \le n - 1, \deg B(x) \le 1\)，那么答案就是好算的。
先考虑怎么求出一组合法的 \(A(x), B(x)\)，满足 \(A(x)(1 - x - x^2) + B(x)(1 - x)^n = 1\)。因为 \(\deg B(x) \le 1\) 所以它比较好求，所以先求 \(B(x)\)。前面那个式子可以看成是对所有 \(x\) 都成立，那么我们代入 \(1 - x - x^2\) 的两个根 \(x_1 = \frac{-1 - \sqrt 5}{2}\) 和 \(x_2 = \frac{-1 + \sqrt 5}{2}\)，得到：
\[\begin{cases} B(x_1)(1 - x_1)^n = 1 \\ B(x_2)(1 - x_2)^n = 1 \end{cases} \]因为 \(\deg B(x) \le 1\) 所以这样可以直接解出 \(B(x)\)。
注意我们现在讨论的都是实数，实现时可以把每个数都用 \(a + b \sqrt 5\) 表示，封装一个结构体即可。
解出 \(B(x)\) 后可以解 \(A(x)\)：
\[A(x) = \frac{1 - B(x)(1 - x)^n}{1 - x - x^2} \]因为能除尽，所以可以直接暴力大除法。
那么此时答案即为：
\[[x^m] \frac{A(x)}{(1 - x)^n} + [x^m] \frac{B(x)}{1 - x - x^2} \]先看左半部分：
\[[x^m] \frac{A(x)}{(1 - x)^n} = \sum\limits_{i \ge 0} [x^i] A(x) \times [x^{m - i}] \frac{1}{(1 - x)^n} = \sum\limits_{i \ge 0} [x^i] A(x) \times \binom{n + m - i - 1}{n - 1} \]组合数可以 \(O(n)\) 预处理前缀积和后缀积后 \(O(1)\) 计算。
再看右半部分（\(f_m\) 为斐波那契数列的第 \(m\) 项）：
\[[x^m] \frac{B(x)}{1 - x - x^2} = [x^m] \frac{ax + b}{1 - x - x^2} = af_m + bf_{m + 1} \]\(f_n\) 可以直接套通项公式计算：
\[f_n = \frac{\sqrt 5}{5} (\frac{1 + \sqrt 5}{2})^n - \frac{\sqrt 5}{5} (\frac{1 - \sqrt 5}{2})^n \]那么这题就做完了。时间复杂度 \(O(n + \log m)\)。
397. BZOJ4671 异或图
设 \(f_i\) 为钦定 \(i\) 个集合两两无边的方案数（即钦定有 \(i\) 个连通块的方案数），设 \(g_i\) 为恰好有 \(i\) 个连通块的方案数，则：
\[f_i = \sum\limits_{j = i}^n {j \brace i} g_j \]根据斯特林反演，得：
\[g_i = \sum\limits_{j = i}^n (-1)^{j - i} \begin{bmatrix} j \\ i \end{bmatrix} f_j \]所以：
\[ans = g_1 = \sum\limits_{i = 1}^n (-1)^{i - 1} (i - 1)! f_i \]问题转化为求 \(f_i\)。
发现 \(n\) 很小，考虑直接枚举哪些点被分到了一个集合（这里的枚举量是贝尔数级别的），设有 \(m\) 个集合。那么每一条两端所属集合不同的边都必须被选偶数次。
设编号为 \(b_{i, 1}, b_{i, 2}, \ldots, b_{i, k}\) 的图包含第 \(i\) 条两端所属集合不同的边，\(a_i\) 为第 \(i\) 个图是否在子集中，那么会得到一个形如 \(\forall i, a_{b_{i, 1}} \oplus a_{b_{i, 2}} \oplus \cdots \oplus a_{b_{i, k}} = 0\) 的异或方程组，高斯消元求其自由元个数 \(c\)，那么这种划分方案对 \(f_m\) 有 \(2^c\) 的贡献。
总时间复杂度 \(O(B_n n^2 (s + n^2))\)。
398. P5748 集合划分计数
显然每个盒子的 EGF 为 \(F(x) = e^x - 1\)。答案的 EGF 为 \(G(x) = e^{F(x)}\)。
标签：le,frac,2024.6,limits,记录,sum,sqrt,deg From： https://www.cnblogs.com/zltzlt-blog/p/18255012