闲话
不是,绝区零真好玩吧?
质疑艾莲,理解艾莲,单推艾莲 /se
从图书馆借了本陶哲轩实分析(
预告:处理▂▕▄▄制▒▟▀问题可以▙依赖[错误: 所引对象未导引至对象实例 ; 标准处理方法_003.rtf 不存在]。不确定能否[已编辑]。
推歌:未名星河 by 蛾君 et al. feat. 洛天依
奇思妙想:一阶常系数非齐次线性递推的远点值
那些你不要的(其*)。
给定 \(p, q_0, \dots, q_m\),定义 \(a_{-1} = 0\),\(\forall n \ge 0, a_{n} = pa_{n - 1} + \sum_{i = 0}^m q_i n^i\)。
求 \(a_n\),其中 \(n\) 较大。
令 \(F(x)\) 为 \(\{a_n\}\) 的 gf,\(G(x)\) 为修正 gf,则直接列出
\[F(x) = pxF(x) + G(x) \]为分析 \(G(x)\),只需要考察 \(\sum_n n^ix^n\)。知道
\[\sum_{n\ge 0} n^ix^n = \sum_{n\ge 0} [t^i/i!] e^{nt} x^n = \left[\frac{t^i}{i!}\right] \frac{1}{1 - xe^t} \]那么
\[G(x) = \sum_{i = 0}^m q_i \left[\frac{t^i}{i!}\right] \frac{1}{1 - xe^t} = \left(\sum_{i = 0}^m q_i \left[\frac{t^i}{i!}\right]\right) \frac{1}{1 - xe^t} \]从而 \(F(x) = G(x) / (1 - px)\),带入得到
\[F(x) = \left(\sum_{i = 0}^m q_i \left[\frac{t^i}{i!}\right]\right) \frac{1}{(1 - px)(1-e^tx)} \]明眼人都能看出来该分式分解了。直接将 Apart[1/((1 - e^t x)(1 - p x)), x]
输入 mma,我们就能得到
直接提取 \(x^n\) 项系数,就能得到答案其实是
\[\left(\sum_{i = 0}^m q_i \left[\frac{t^i}{i!}\right]\right)\frac{e^{(n + 1)t} - p^{n + 1}}{e^t - p} \]瓶颈是提取后面那个东西的前 \(m\) 项系数,直接模 \(x^{m + 1}\) 意义下求逆就是 \(O(m \log m)\) 的。
不太懂能不能做到 \(O(m)\),根据伯努利数 gf 不微分有限的经验,我们可能需要一些不依赖 dfinite 的做法。
一个 motivation 是 egf 和 ogf 的转换。那么答案就是
\[\left(\sum_{i = 0}^m q_i \left[t^i\right]\right)\sum_{i = 0}^n\frac{p^{n - i}}{1 - it} \]然后咋办啊?
标签:right,frac,17,闲话,sum,24.7,gf,px,left From: https://www.cnblogs.com/joke3579/p/18306766/chitchat240717