那些你不要的（1）2021.4.27 ~ 2021.6.12
Elegia
2021-06-20 21:06:36
# 4 月 27 日
尝试使用新方法计算 $n \brack k$，**没有实质突破**。
主要想法是根据 Lagrange 反演公式，首先有转化
$$
\begin{aligned}
n \brack k &= n![z^n] \frac 1{k!} \left( \ln \frac 1{1-z}\right)^k\\
&= (n-1)! [z^{n-k}] \frac 1{(k-1)!} \left( \frac z{1-e^{-z}} \right)^n
\end{aligned}
$$
虽然 Bernoulli 数的单项已经可以 $\Theta(n)$ 计算，但是其原因在于 GF
$$
\frac z{e^z - 1} = \frac{\ln (1 + (e^z - 1))}{e^z - 1}
$$
其分子是 $\ln(1+G)$ 的一次幂，这个幂次增大的时候又回到了 $n\brack k$ 这个问题本身。
但有趣的是，我们至少得到了一个新的组合恒等式。
$$
\left.{n\brack k} \middle/ \binom{n-1}{k-1}\right. = \sum_m \left.(-1)^{n-k-m} {n-k \brace m} {n + m \brack n} \middle/ \binom{n+m}{n} \right.
$$
--------
计数型的树上背包，对 $q$ 个点求答案**可以做到 $\Theta(n^2 + qn\log n)$**。这里对问题的定义为：给定一个可以 $\Theta(n)$ 进行的线性变换 $\mathbf T$ 且该变换只使一个多项式的次数增加 $1$。每个点的多项式即为将各子树的多项式乘积施变换 $\mathbf T$。另给定一个向量 $\boldsymbol a$，每个点的答案即该点多项式的系数向量与 $\boldsymbol a$ 的点积。
我们先任选一根 $\Theta(n^2)$ 预处理出自底向上的乘积。考虑取阈值 $L$，对于所有子树大小 $\ge L$ 的节点，计算出其自顶向下的乘积。由于这些节点总共只有 $n/L$ 个叶子，那么形成的树只有 $n/L$ 个分叉，我们在分叉处可以直接通过 FFT 计算答案，而其余情况的转移代价总和是 $\Theta(n^2)$。此时预处理总共消耗 $\Theta(n^2) + n/L \cdot \Theta(n\log n)$ 的时间。
而一次询问时，考虑取其所在的最深祖先处，首先需要消耗 $\Theta(n\log n)$ 进行一次卷积，然后再消耗 $\Theta(nL)$ 的时间定位到其。此时取 $L=\log n$ 便得到复杂度 $\Theta(n^2 + qn\log n)$。
# 4 月 29 日
「数据删除」
# 5 月 1 日
「数据删除」
# 5 月 3 日
将 [Codeforces Global Round 14 E](https://codeforces.com/problemset/problem/1515/E) 的计算改进。
放置一定是若干连续段，且每段的放置顺序单峰，容易发现答案可表为下式
$$
\sum_{k\ge 0} (k+1)! {n-k \brace k+1} 2^{n-2k-1}
$$
因此生成函数即为
$$
\sum_{k\ge 0} \frac{(k+1)!x^{2k+1}}{(1-2x)\cdots(1-2(k+1)x)}
$$
分治计算，可以**在 $\Theta\left(\mathsf{M}(n)\log n\right)$** 时间内求出 $1\sim n$ 的答案。
而利用第二类 Stirling 数的容斥展开式，我们可以将上式变换为
$$
-x^{-1} + \sum_{j\ge 0} \frac {x^{-1}}{1-2jx} \frac{(x/2)^j}{(1+x/2)^{j+1}}
$$
# 5 月 4 日
在 $\Theta(\mathsf{M}(n)\log n)$ 时间计算一条从 $(0,0)$ 走出的路径，各点处的 $x \brack y$ 值。
考虑将问题看做一个线性算法 $(a_i) \rightarrow \sum a_i {x_i \brack y_i}$ 的转置。考虑将其扩展为计算
$$
\sum a_i t^{-y_i} t^{\overline{x_i}}
$$
那么根据 $x_i,y_i$ 是游走给出的，可知 $t^{-y_i} t^{\overline{x_i}}$ 每次都是上一个多项式乘以一个简单分式，分治计算即可。
此法也可以处理 ${x \brace y}$ 的情况。
# 5 月 9 日
「数据删除」
# 5 月 10 日
简单尝试小模数下的代数问题。对于一个首一 $d$ 次多项式 $f(x)$，考虑计算 $f(x)^{1/2}$ 的系数。取模一小奇素数 $p$。
首先如果只计算 $n$ 次项系数，那么可以考虑 $1/2$ 的 $p$ 进展开。变成 $[x^n]q(x)f(x)^{\sum_{i\ge 0} a_ip^i}$ 的问题。我们一开始将 $n$ 写作 $\sum_{i\ge 0}n_i p^i$，将 $1/2\in \mathbb Z_p$ 写作 $\sum_{i\ge 0}a_ip^i$。
经过适当的预处理后，我们计算 $[x^n]p(x)f(x)^{a_0} f(x^p)^{\sum_{i\ge 1}a_ip^{i-1}}$ 这一过程。其**复杂度为 $\Theta(d^2\log_p n)$**。和 [LibreOJ P577 简单算术](https://loj.ac/p/577)一致。
如果是要求 $0\sim n$ 的系数呢？设 $g(x)^2 = f(x)$，我们考虑等式
$$
\begin{aligned}
g(x^p) &= g(x)^p \\
&= g(x) f(x)^{\frac{p-1}2}
\end{aligned}
$$
对于 $p\nmid n$ 的时候，我们可以根据微分方程得到一个 $\Theta(d)$ 的递推式，而 $p\mid n$ 的时候，我们 $\Theta(pd)$ 进行计算，这里的贡献是 $n/p \cdot \Theta(pd)$ 的。**总共复杂度为 $\Theta(nd)$**。
但是目前的计算复杂度总是依赖 $p$ 有关的预处理，以及刚刚的问题中由于要计算 $f(x)^{\frac{p-1}2}$，这个做法只能适用于度数小的多项式，而不能用于稀疏多项式。
# 5 月 11 日
但事实上昨天的问题对任意幂**都可以等复杂度**。由 $g(x)=f(x)^{a_0}f(x^p)^{\sum_{i\ge 1}a_ip^{i-1}}$，我们只需将 $f(x)^{\sum_{i\ge 1}a_ip^{i-1}}$ 算到第 $n/p$ 项，复杂度为 $T(n) = \Theta(nd) + T(n/p)$ 也即 $\Theta(nd)$。
------
如何计算一个多项式进行 $k$ 次求和后的系数？首先我们可以计算 $\left(\frac x{e^x-1}\right)^k$ 的系数，因为一个多项式 $f(x)$ 的 $k$ 次不定求和可以直接用 $\frac 1{(e^{\mathrm D}-1)^k} f$ 刻画。但是我们还需要定出 $c_0 + c_1x + \cdots + c_{k-1}x^{k-1}$ 这部分。
首先我们需要精确地定义出求和，常见左闭右开和左闭右闭。
- 左闭右开：$f_{k+1}(x) = \sum_{0\le j {\color{red}<} x} f_{k}(j)$，我们注意在这个定义下 $f_k(0),f_k(1),\dots,f_k(k-1)=0$，也就有 $x^{\underline k}\mid f_k(x)$，这就简单了，对直接一次卷积得到的 $\hat f_k$ 来说。我们减去 $\hat f_k \bmod x^{\underline k}$ 就得到了实际答案。
- 左闭右闭：$f_{k+1}(x) = \sum_{0\le j {\color{red}\le} x} f_{k}(j)$，这里其实有 $(x+k)^{\underline k} \mid f_k$，一个简单的解释是 $\binom x j$ 进行 $k$ 次这样的求和后得到的是 $\binom{x+k}{j+k}$，而这样的二项式线性组合出了原多项式。注意一开始我们要用 $\frac {e^{k\mathrm{D}}}{(e^{\mathrm D}-1)^k} f$。
这样，我们就在 $\Theta(\mathsf{M}(n+k))$ 的时间内完成了。
# 5 月 12 日
尝试计算一些二项和问题。首先考虑
$$
\begin{aligned}
& \quad \sum_{k} \binom{2k}k \binom{n}{n-2k}\\
&= [x^n] \frac 1{\sqrt{1-4x^2}} (1+x)^n\\
&= [x^n] \frac 1{\sqrt{1-4\left(\frac x{1-x}\right)^2}} \frac 1{1-x}\\
&= [x^n] \frac 1{\sqrt{1-2x-3x^2}}
\end{aligned}
$$
这种二项和的 D-Finite 性质当然是显然的，我们更感兴趣的是其 Algebraic 性质。有了刚刚的式子之后，我们可以很容易地对任何奇素数 $p$ 算其 $\bmod p$ 的任意一项了，因为设 $f(x)=(1-2x-3x^2)^{\frac{p-1}2}$，其次数是 $p-1$，递归过程没有除法。并且有
$$
(1-2x-3x^2)^{-1/2} = f(x)f(x^p)\cdots
$$
因此我们就有 $a_n \equiv a_{n\bmod p} a_{\lfloor n/p \rfloor}$。
不过看起来对于处理形如 $\binom {2k}k$ 来说，另一条思路可能更具前途。我们直接利用 $\binom{2k}{k}=[x^0](1+x)^{2k}x^{-k}$，就有
$$
\begin{aligned}
& \quad \sum_k \binom{2k}k \binom{n}{n-2k}\\
&= \sum_k \binom{n}k [x^0] (1+x^2)^k x^{-k}\\
&= [x^0] \left( x^{-1} + 1 + x \right)^k
\end{aligned}
$$
那么如果我们模素数 $p$，就有
$$
[x^0] \left( x^{-1} + 1 + x \right)^k = [x^0] \left( x^{-1} + 1 + x \right)^{k\bmod p} \left( x^{-p} + 1 + x^p \right)^{\lfloor k/p\rfloor}
$$
发现两部分独立，可以直接分离了。这样的证明就是天然对 $p=2$ 也成立的。
我们又考虑稍微复杂点的组合式
$$
\begin{aligned}
&\quad \sum_{2(i+j) = n} \binom{2i}i \binom{2j}j \binom{n}{2i}\\
&= \sum_i \binom n i [x^0](x^{-1}+x)^i [y^0](y^{-1}+y)^{n-i}\\
&= [x^0y^0](x^{-1}+x+y^{-1}+y)^n\\
&= [u^0v^0]((u^{-1}+u^1)(v^{-1}+v^1))^n \quad x=uv, y = u/v\\
&= \binom{n}{n/2}^2
\end{aligned}
$$
由此，我们可以尝试冲击一大类组合和式的同余性质了。设 $m$ 阶整数拆分 $\lambda \vdash n$，那么设序列
$$
a_k = k![x^k] \left( \sum_{i\ge 0} \frac{x^{\lambda_1 i}}{i!^{\lambda_1}} \right)\cdots \left( \sum_{i\ge 0} \frac{x^{\lambda_m i}}{i!^{\lambda_m}} \right)
$$
不难发现其是个整数数列，我们断言对任意素数 $p$ 有
$$
a_k \equiv a_{k\bmod p} a_{\lfloor k/p \rfloor} \pmod p
$$
方法是我们进行构造，转化为数列
$$
[x_1^0\dots x_n^0] \frac 1{1-t(x_1/x_2 + \cdots + x_{\lambda_1-1}/x_{\lambda_1} + x_{\lambda_1}/x_1) - \cdots}
$$
记 $Q(t,x_1,\dots,x_n) = 1-t(x_1/x_2 + \cdots + x_{\lambda_1-1}/x_{\lambda_1} + x_{\lambda_1}/x_1) - \cdots$，那么由
$$
[x_1^0\dots x_n^0] \frac 1{Q(t,x_1,\dots,x_n)} = [x_1^0\dots x_n^0] \frac {Q(t,x_1,\dots,x_n)^{p-1}}{Q(t^p,x_1^p,\dots,x_n^p)}
$$
观察系数即可得到结果。
# 5 月 16 日
「数据删除」
# 5 月 31 日
让我们继续扩展 [UOJ 633 你将如闪电般归来](https://uoj.ac/problem/633)。考虑将其拓展为输入一个度数为 $d$ 的多项式 $f(x)$。
那么考虑 $F_{d}(x) = f^{(d)}(\sinh^{-1} x)$。那么就有
$$
\begin{aligned}
F_{d}'(x) &= f^{(d+1)}(\sinh^{-1} x) (\sinh^{-1}x)'\\
&= F_{d+1}(x) \cdot \frac 1{\sqrt{1+x^2}}\\
F_{d}''(x) &= F_{d+2}(x) \cdot \frac 1{1+x^2} - F_{d+1}(x) \cdot \frac x{(1+x^2)^{3/2}}\\
&= F_{d+2}(x) \cdot \frac 1{1+x^2} - F_d'(x) \cdot \frac x{1+x^2}\\
(1+x^2)F_{d}''(x) &= F_{d+2}(x) - xF_d'(x)
\end{aligned}
$$
两边提取 $[x^n]$，得
$$
\begin{aligned}
(n+2)(n+1)f_{d,n+2} + n(n-1)f_{d,n} &=
f_{d+2,n} - nf_{d,n}\\
(n+2)(n+1)f_{d,n+2} + n^2f_{d,n} &=
f_{d+2,n}
\end{aligned}
$$
进行 $k$ 次积分，就有 $f_{d,n} = (n+k)^{\underline k}g_{d,n+k}$。即得
$$
\begin{aligned}
(n+2)(n+1) (n+k+2)^{\underline k}g_{d,n+k+2} + n^2 (n+k)^{\underline k}g_{d,n+k} &=
(n+k)^{\underline k} g_{d+2,n+k}\\
(n+2)(n+1) (n+k+2)(n+k+1)g_{d,n+k+2} + n^2 (n+2)(n+1)g_{d,n+k} &=
(n+2)(n+1) g_{d+2,n+k}
\end{aligned}
$$
约分后有
$$
n(n-1)g_{d,n} + (n-k-2)^2g_{d,n-2} =
g_{d+2,n-2} + C_1\delta_{n-k-1} + C_2\delta_{n-k}
$$
有微分方程
$$
k^2 G_d(x) + (1-2k)xG_d'(x) + (1+x^2)G_d''(x) = G_{d+2}(x) + C_1x^{k-1} + C_2x^{k-2}
$$
令 $X=\frac{x-1/x}2,H_d(x)=G_d(X)$，有
$$
\begin{aligned}
&\quad k^2(1+x^2)H_d(x)\\
&+((1+2k)x+(1-2k)x^3)H_d'(x)\\
&+(x^2+x^4)H_d''(x)\\
&= (G_{d+2}(x) + C_1X^{k-1} + C_2X^{k-2})(1+x^2)
\end{aligned}
$$
可以预见的是，这是一个 $\Theta(d^2 k)$ 求系数的算法。能不能把 $d$ 去掉一个，怀疑这涉及到某种非常深刻的矛盾，今天先到这里。
# 6 月 12 日
考虑证明一个恒等式：
$$
[x^ny^n] (1+x)^k (1+y)^l (1-xy)^{-k-l-1} = \binom{n+k}n\binom{n+l}n
$$
我们首先考虑扩元，用 $u,v$ 统计 $k,l$ 的次数：
$$
\begin{aligned}
&= [x^ny^nu^kv^l] \frac 1{1-u(1+x)/(1-xy)}\frac 1{1-v(1+y)/(1-xy)} \frac 1{1-xy}\\
&= [x^ny^nu^kv^l] \frac 1{1-xy-u(1+x)}\frac 1{1-xy-v(1+y)} (1-xy)
\end{aligned}
$$
考虑约束的 $x^ny^n$，我们换元 $x=st,y=t^{-1}$，就有
$$
\begin{aligned}
&= \frac1{1-s-u(1+st)}\frac 1{1-s-v(1+t^{-1})}(1-s)\\
&= \frac1{1-ust/(1-s-u)} \frac 1{1-s-u} \frac 1{1-vt^{-1}/(1-s-v)} \frac 1{1-s-v} (1-s)
\end{aligned}
$$
那么提取 $[t^0]$ 就有
$$
\begin{aligned}
&= \frac1{1-\frac{uvs}{(1-s-u)(1-s-v)}} \frac 1{1-s-u} \frac 1{1-s-v} (1-s)\\
&= \frac {1-s}{(1-s-u)(1-s-v)-uvs}\\
&= \frac {1-s}{(1-s)^2 -(u+v)(1-s) + uv(1-s)}\\
&= \frac 1{1-s-u-v-uv}\\
&= \frac 1{(1-u)(1-v)} \frac 1{1-\frac s{(1-u)(1-v)}}\\
[s^nu^kv^l] \bullet &= \binom {n+k}n \binom{n+l}n
\end{aligned}
$$