那些你不要的（1）2021.4.27 ~ 2021.6.12
Elegia
·
·
个人记录
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 的计算改进。
放置一定是若干连续段，且每段的放置顺序单峰，容易发现答案可表为下式
\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 简单算术一致。
如果是要求 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 你将如闪电般归来。考虑将其拓展为输入一个度数为 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}