最新要闻
- 荣耀Magic 5系列镜头模组曝光:经典圆形设计、配100X长焦
- 每日观点:地表最快!realme宣布首发量产240W满级秒充:充满不到10分钟
- 李国庆称腾讯京东有大公司病 当当就是失败的案例
- 98年哥哥返乡给15个弟妹买一车礼物:塞满整个后备箱
- 荣耀MagicOS获新浪2022科技风云榜年度智能操作系统奖
- 锐龙9 6900HX加持!魔方M600迷你主机图赏
- 【世界报资讯】便宜还好用:绿联iPhone全系钢化膜冲量3.6元/张
- 世界速看:折叠屏我只认OPPO Find N2:安卓阵营独一无二
- 环球聚焦:宝马展示i Vision Dee概念汽车:可变换车身颜色 有科幻味了
- 全球视点!员工:不怕大家拿任何手机跟一加11比精致度和质感
- 天天快资讯丨天府可乐因破产传闻销量暴增 民族品牌不会轻易垮:请理性消费
- 144MB暴力缓存!AMD锐龙7000 3D缓存版杀来:16核心神奇120W
- 马斯克最“惨” 福布斯:2022年美国亿万富翁身价创纪录暴跌
- 全球即时看!独立包装、现货速发:掌护快速检测试剂盒2.9元/份
- 世界微头条丨李斌发蔚来全员信:列举8大问题 有同行比我们更出色
- 全球热议:比亚迪宋PLUS上月热销50006台:接棒哈弗H6成新一代神车
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
每日快看:浅谈多项式与生成函数
本文源码约 34k,可能需要一段时间加载 \(\LaTeX\)。
(资料图片仅供参考)
首先需要注意的是,本文中将不会涉及具体的程式化求解,即与代码实现无关。同样的,阅读本文需要你掌握基础的快速傅里叶变换理论知识,并已理解如何对多项式进行形式化操作。本文只会初步地涉及计数需要的手法和套路,具体的讲解就留待以后的文章吧。
如果读者认为本文存在内容的缺漏或错误,请在评论区指出,我会在收到后第一时间处理。
目录- \(1.\) 多项式与幂级数
- \(1.1\) 基础定义
- \(1.2\) 多项式牛顿迭代
- \(1.3\) 形式 \(\text{Laurent}\) 级数
- \(1.4\) 拉格朗日反演
- \(1.5\) 分式分解
- \(2.\) 生成函数(\(\underline{\textbf{G}}\text{enerating} \ \underline{\textbf{F}}\text{unction}, \ \text{GF}\))
- \(2.1\) 定义及性质
- \(2.2\) 常用的形式操作和 \(\text{OGF}\)
- \(2.3\) 例题
- \(2.3.1\):找零问题
- \(2.3.2\):斐波那契数列
- \(2.3.3\):卡特兰数
- \(2.4\) 简析生成函数
- \(2.4.1 \text{ OGF}\)
- \(2.4.2 \text{ EGF}\)
- \(2.4.3 \text{ DGF}\)
- 附录
- 附 \(1.\) 经典微积分
- 附 \(2.\) 离散微积分
- 附 \(3.\) 一些具体的级数
- \(3.1\) 广义二项级数
- \(3.2\) 广义指数级数
\(1.\) 多项式与幂级数
\(1.1\) 基础定义
\(\textbf{定义 1.1.1 } \text{(多项式) }\)
一个多项式 \(f\) 形如
\[f(x) = \sum_{i=0}^n a_i x^i,\quad a_n\neq 0\]
其中 \(a_i\) 被称为多项式 \(f\) 的第 \(i\) 项系数;\(n\) 被称为多项式 \(f\) 的度数(次数),记为 \(\deg f\)。度数有时可以取 \(\infty\)。一般地,记 \(f(x)\) 的第 \(i\) 项系数为 \([x^k]f(x)\) 或 \(f[i]\)。为简便,带入占位元 \(x\) 时的多项式 \(f(x)\) 一般记作 \(f\)。由一些基础数学知识可以知道,一个 \(n\) 次多项式的系数和 \(n + 1\) 个点值是可以互相唯一地得到的。由系数得到点值的操作被称为多点求值,由点值得到系数的操作被称为插值。
在接下来的内容中,我们一般不关心当 \(x\) 为某个特定的值时 \(f(x)\) 的取值,而会将它作为一个操作系数的工具使用,一般称之为操作对象。我们认为 \(x\) 只是一个占位符,起到对系数的标识作用。
很多时候我们无力操作度数过于大的多项式,这就需要一个度数的界 \(\pmod {x^n}\) 来限制。如果度数均是非负整数,且运算均由卷积定义,在操作中我们可以只保留界以内的信息。\(F(x) \bmod x^n\) 被称作 \(F\)(在 \(n\) 次项内)的一个截取。
对于一般的环 \(R\),定义 \(R\) 上的所有多项式组成一个多项式环 \(R[x]\)。这其中的任意元素 \(f\) 都可以表示为 \(\langle f_n\rangle\) 的形式。如果考察度取到 \(+\infty\) 的 \(f\),我们称 \(f\) 的全体组成一个形式幂级数环 \(R[[x]]\),其中的任意元素 \(f\) 都被称作一个形式幂级数,可以简称幂级数。在 OI 应用中,\(R\) 一般定义在一个模 \(p\) 的整数集 \(\mathbb F_p\) 上。更特殊地,\(p\) 可以被分解为 \(a\times 2^k + 1\) 的形式,其中 \(k\) 应当较大。同时,下文中更常见的是对无穷序列的操作,只是在某个特殊位置截断,这时更应当称其为幂级数。然而,多项式和幂级数都只是用于指代我们所操作对象的名称,具体含义应视上下文而定。
定义对一个常数项为 \(0\) 的幂级数 \(f(x)\) 进行左移得到 \(\dfrac{f(x)}{x}\)。定义对一个幂级数 \(f(x)\) 进行右移得到 \(xf(x)\)。
操作多项式的核心是两个多项式的乘法,这个操作又称卷积。
\(\textbf{定义 1.1.2 } \text{(卷积/乘法) }\)
给定两个多项式 \(f, g\),度数分别为 \(n, m\)。二者的卷积/乘法 \(f\times g\) 定义如下:
\[f\times g = \sum_{i=0}^n \sum_{j=0}^m f[i]g[j] x^{i + j}\]
可以发现卷积得到的多项式的度数是给定多项式的度数相加。从系数的角度去观察,推得
\[[x^k](f\times g) = \sum_{i = 0}^k f[i]g[k - i]\]承接上文对 \(p\) 的讨论。当 \(R\) 上存在 \(2^k\) 次单位根时,快速傅里叶变换允许我们在 \(O(k2^k)\) 的时间复杂度内计算两个多项式的乘法。这类整数集对应的模数 \(p\) 又被称作 NTT 模数,常见的有 \(998244353,\ 1004535809,\ 167772161\) 等。
然后有了乘法就能自然定义除法和取模。
\(\textbf{定义 1.1.3 } \text{(带余除法) }\)
给定两个多项式 \(f, g\),度数分别为 \(n, m\)。存在唯一的 \(Q, R\) 满足
\[f(x) = Q(x) g(x) + R(x) \quad \deg R < \deg g\]当 \(\deg f \ge \deg g\) 时 \(\deg Q = \deg f - \deg g\),反之 \(=0\)。我们称 \(Q\) 为 \(f\) 除 \(g\) 的商,\(R\) 为 \(f\) 除 \(g\) 的余数。
幂级数乃至有理函数的复合是下文中很重要的一类操作,尤其在应用拉格朗日反演时。因此这里首先介绍复合。
\(\textbf{定义 1.1.4 } \text{(复合) }\)
给定两个多项式 \(f, g\),度数分别为 \(n, m\)。二者的复合 \(f\circ g\) 定义如下:
\[f\circ g = \sum_{i=0}^n f[i] g(x)^i\]\((f\circ g)(x)\) 又常记作 \(f(g(x))\)。
\(\textbf{定义 1.1.5 } \text{(复合逆) }\)
给定一个多项式 \(f\)。\(f\) 的复合逆 \(f^{\langle -1 \rangle}\) 是满足 \(f\circ f^{\langle -1 \rangle} = x\) 的函数。
对于 DFT 相关的定义,可以查阅本博客。
\(1.2\) 多项式牛顿迭代
在第二节的描述中,我们常常使用递归构造的幂级数作为操作对象。这常常是由于幂级数由给定的递推式获得,我们现在需要做的就是先获得求解递归构造的幂级数的方法。一个幂级数 \(F(x)\) 是递归构造的,就是在说 \(F(x)\) 可以由形如 \(F(x) = G(F(x))\) 的式子得到。我们通常通过多项式牛顿迭代来获得 \(F(x)\) 的一个截取。在牛顿迭代的过程中度数是倍增的,因此牛顿迭代本身一般不会带来复杂度的增加。
我们首先引出泰勒展开的形式。
\(\textbf{定义 1.2.1 } \text{(泰勒展开) }\)
对于一个多项式 \(F(x)\),我们可以从 \(a\) 点处采用高阶导数用无穷级数展开它,即
\[F(x) = \sum_{i=0}^{\infty}\frac{F^{(i)}(a)}{i!}(x - a)^i\]
在数学分析上,更实用的是 \(a = 0\) 的情况,这时得到的无穷级数被称作麦克劳林级数。
\(\textbf{定义 1.2.2 } \text{(麦克劳林级数) }\)
如上地写出形式,得到
\[F(x) = \sum_{i=0}^{\infty}\frac{F^{(i)}(0)}{i!}x^i\]
可以发现这是一个幂级数的形式。我们可以通过麦克劳林级数导出一些简单的形式,通过卷积来定义一些东西。经典例子是 \(e^x = \sum_{i=0}^{\infty}x^i / i!\)。
下面给出多项式牛顿迭代的一般形式。
\(\textbf{引理 1.2.1 } \text{(牛顿迭代) }\)
给定两个多项式 \(F, G\)。若 \(G(F(x)) = 0\),且我们已知 \(G(F_0(x)) \equiv 0 \pmod{x^{n}}\),则满足 \(G(F(x)) \equiv 0 \pmod{x^{2n}}\) 的目标多项式 \(F\) 由下式给出:
\[F(x) = F_0(x) - \frac{G(F_0(x))}{G"(F_0(x))}\]
证明:
由于 \(F(x)\) 也满足 \(G(F(x)) \equiv 0 \pmod{x^{n}}\),因此 \(F(x) - F_0(x) \equiv 0 \pmod{x^n}\),即 \(F(x) - F_0(x)\) 的最低次项次数 \(\ge n\)。
我们将 \(G(F(x))\) 在 \(F_0(x)\) 处展开,得到
\[G(F(x)) = \sum_{i=0}^{\infty} G^{(i)}(F_0(x)) \frac{(F(x) - F_0(x))^i}{i!}\]由于 \(i > 1\) 时 \((F(x) - F_0(x))^i\) 最低次项次数 \(\ge 2n\),因此在 \(x^{2n}\) 处截断后 \(i > 1\) 的项都是不必要的。因此得到
\[G(F(x)) = G(F_0(x)) + G"(F_0(x)) (F(x) - F_0(x))\]整理即可得到牛顿迭代的表达形式。
关于优化该做法常数的方式,可以查阅关于优化形式幂级数计算的 Newton 法的常数, negiizhao。然而需要注意的是,费脑子卡你板子的常还不如先打一个半在线卷积
\(1.3\) 形式 \(\text{Laurent}\) 级数
我们可以构造一类非正式的幂级数,满足其最低次项为 \(n_0 \in \mathbb Z\)。这种级数被称作形式 \(\text{Laurent}\) 级数。形式 \(\text{Laurent}\) 级数可以看作是普通幂级数的一种延拓。首先给出定义。
\(\textbf{定义 1.3.1 }\text{(形式 Laurent 级数)}\)
一个最低次项为 \(n_0\) 次的形式 \(\text{Laurent}\) 级数 \(A(x)\) 被定义为
\[A(x) = \sum_{i=n_0}^{\infty} a_i x^i\]
注意对于不同的两个形式 \(\text{Laurent}\) 级数,二者的 \(n_0\) 可能不同。可以看到,\(n_0 \ge 0\) 的形式 \(\text{Laurent}\) 级数就是普通的幂级数。形式 \(\text{Laurent}\) 级数的形式运算和正常幂级数类似,下面只对除法进行展开。
对于两个形式 \(\text{Laurent}\) 级数的除法运算,需要先对其作转化。我们将 \(A(x)\) 改写成如下形式:
\[x^{n_0} \sum_{i \ge 0} a_{i + n_0} x^i\]即 \(x^{n_0}\) 乘上一个幂级数的形式。对于 \(n_0\) 分别为 \(n_a, n_b\) 的两个形式 \(\text{Laurent}\) 级数 \(A, B\),定义 \(A / B\) 的结果是一个形式 \(\text{Laurent}\) 级数 \(C\),满足
\[C(x) = x^{n_a - n_b} \frac{\sum_{i\ge 0} a_{i + n_a} x^i}{\sum_{i \ge 0} b_{i + n_b} x^i}\]因此 \(C\) 是一个 \(n_0 = n_a - n_b\) 的形式 \(\text{Laurent}\) 级数。
可以发现,形式 \(\text{Laurent}\) 级数可以通过系数的位移采用经典幂级数表示,但我们为何要定义如此的一个函数呢?答案将随着接下来对形式留数的探讨揭晓。
\(\textbf{定义 1.3.2 }\text{(形式留数)}\)
一个形式 \(\text{Laurent}\) 级数的形式留数为 \(x^{-1}\) 次项前的系数。
自然地,可以得出以下引理:
\(\textbf{引理 1.3.1 }\)
一个形式 \(\text{Laurent}\) 级数求导后形式留数为 \(0\)。
注意到 \(x^0\) 在求导后系数不会传递给 \(x^{-1}\),而 \(x^{-1}\) 在求导后系数会传递给 \(x^{-2}\)。
\(\textbf{引理 1.3.2 }\)
对于 \(n_0 = 1\) 的形式 \(\text{Laurent}\) 级数 \(A(x)\),\(A"(x)A^k (x)\) 的形式留数为 \([k = -1]\)。
当 \(k \neq -1\) 时,\(A"(x)A^k(x) = \left(A^{k + 1}(x) / (k + 1)\right)"\),由引理 \(1.3.1\) 得到其为 \(0\);当 \(k = -1\) 时,
\[\frac{A"(x)}{A(x)} = x^{-1} \frac{1 + \frac{2a_2}{a_1}x + \frac{3a_3}{a_1}x^3 + \cdots}{1 + \frac{a_2}{a_1}x + \frac{a_3}{a_1}x^3 + \cdots}\]后面的分式是一个 \(n_0 = 0\) 且常数项为 \(1\) 的形式 \(\text{Laurent}\) 级数,从而得证。
到了这里,我们就可以用形式 \(\text{Laurent}\) 级数来做一些事情了。具体地,我们将证明一系列拉格朗日反演公式。
\(1.4\) 拉格朗日反演
\(\textbf{定理 1.4.1 }\text{(拉格朗日反演)}\)
给定一个 \(n_0 = 1\) 的形式 \(\text{Laurent}\) 级数 \(Q(x)\)。对于任意整数 \(n, k\),有
\[n[x^n]Q^k(x) = k[x^{-k}]\left(Q^{\langle -1\rangle}(x)\right)^{-n}\]
证明:
我们将复合逆的定义两边求 \(k\) 次方得到
\[Q^k (Q^{\langle -1\rangle}(x)) = x^k\]两边求导。这里强调 \(f"(x)\),记作 \((f)"(x)\)。
\[\left(Q^{\langle -1\rangle}(x)\right)" \left(Q^k\right)"\left(Q^{\langle -1\rangle}(x)\right) = k x^{k-1} \]两边乘 \(\left(Q^{\langle -1\rangle}(x)\right)^{-n}\),同时将函数 \((Q^k)"\) 展开,得到
\[\left(Q^{\langle -1\rangle}(x)\right)" \left(\sum_{i} i [z^i]Q^k(z) \times \left(Q^{\langle -1\rangle}(x)\right) ^{i - 1 - n} \right) = k x^{k-1}\left(Q^{\langle -1\rangle}(x)\right)^{-n} \]我们把最前面的 \(\left(Q^{\langle -1\rangle}(x)\right)"\) 和 \(\left(\left(Q^{\langle -1\rangle}(x)\right) ^{i - 1 - n} \right)\) 乘起来,得到引理 \(1.3.2\) 的形式,并取左右两边的形式留数,得到
\[\sum_{i} i [z^i]Q^k(z) \times [x^{-1}] \left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right) ^{i - 1 - n} = [x^{-1}]k x^{k-1}\left(Q^{\langle -1\rangle}(x)\right)^{-n} \]由引理 \(1.3.2\),只有 \(n = i\) 时才有贡献,这就得到了
\[n [z^n]Q^k(z) = k [x^{-k}]\left(Q^{\langle -1\rangle}(x)\right)^{-n} \]得证。
\(\textbf{定理 1.4.2 }\text{(拓展拉格朗日反演)}\)
给定一个形式 \(\text{Laurent}\) 级数 \(P(x)\) 和一个 \(n_0 = 1\) 的形式 \(\text{Laurent}\) 级数 \(Q(x)\)。对于非零整数 \(n\),有
\[[x^n] P(Q(x)) = \frac{1}{n} [x^{n-1}]P"(x) \left(\frac{x}{Q^{\langle -1 \rangle}(x)}\right)^n\]
我们只需要针对 \(P(x) = px^k\) 的形式验证即可。对于 \(P\) 由多项组成的情况可以求和解决。
两边变成
\[p[x^n] Q^k(x) = \frac{p}{n} [x^{-1}] k x^{k-1} \left(Q^{\langle -1 \rangle}(x)\right)^{-n}\]这其实就是定理 \(1.4.1\) 的形式。
拓展拉格朗日反演的形式往往更适合 OI 中的计算,这是由于 \(Q^{\langle -1 \rangle}\) 是一个幂级数,而当 \(P\) 也是幂级数时整个的形式就很友好了。只要我们能计算复合逆,我们就能直接转成幂级数的操作。复合逆的计算一般采用迭代。
当然这两个公式在一些情况下的应用不是很顺畅。因此 EI 提出了另类拉格朗日反演,形式如下。
\(\textbf{定理 1.4.3 }\text{(另类拉格朗日反演)}\)
给定一个 \(n_0 = 1\) 的形式 \(\text{Laurent}\) 级数 \(Q(x)\)。对于任意整数 \(n, k\),有
\[[x^n] Q^k(x) = [x^{-k-1}] \left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{-n-1}\]
仍然考虑从复合逆的定义两边 \(k\) 次方入手。
\[Q^k (Q^{\langle -1\rangle}(x)) = x^k\]不需要求导,直接将左边展开并乘入右边缺的 \(\left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{-n-1}\)。
\[\sum_{i} [z^i] Q^k(z) \left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{i-n-1}= x^k\left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{-n-1}\]两边取形式留数得到
\[\sum_{i} [z^i] Q^k(z) [x^{-1}] \left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{i-n-1}= [x^{-k-1}]\left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{-n-1}\]同样考虑只有 \(n = i\) 时有贡献。得到
\[[z^n] Q^k(z) = [x^{-k-1}]\left(Q^{\langle -1\rangle}(x)\right)"\left(Q^{\langle -1\rangle}(x)\right)^{-n-1}\]得证。
同样的手法可以用于求得更实用的形式。(该叫拓展另类拉格朗日反演?)
\(\textbf{定理 1.4.4 }\text{(另类拉格朗日反演)}\)
给定一个形式 \(\text{Laurent}\) 级数 \(P(x)\) 和一个 \(n_0 = 1\) 的形式 \(\text{Laurent}\) 级数 \(Q(x)\)。对于整数 \(n\),有
\[[x^n] P(Q(x)) = [x^{n}]P(x) \left(Q^{\langle -1\rangle}(x)\right)" \left(\frac{x}{Q^{\langle -1 \rangle}(x)}\right)^{n + 1}\]
我们只需要针对 \(P(x) = px^k\) 的形式验证即可。对于 \(P\) 由多项组成的情况可以求和解决。
两边变成
\[p[x^n] Q^k(x) = p [x^{n - k - n - 1}] \left(Q^{\langle -1\rangle}(x)\right)" \left(Q^{\langle -1 \rangle}(x)\right)^{- n - 1}\]这其实就是定理 \(1.4.3\) 的形式。
重新写出常用的两个拉格朗日反演形式:
\[[x^n] P(Q(x)) = \frac{1}{n} [x^{n-1}]P"(x) \left(\frac{x}{Q^{\langle -1 \rangle}(x)}\right)^n\]\[[x^n] P(Q(x)) = [x^{n}]P(x) \left(Q^{\langle -1\rangle}(x)\right)" \left(\frac{x}{Q^{\langle -1 \rangle}(x)}\right)^{n + 1}\]然后我们就能用他们去推导一系列问题了。应用牛顿迭代和拉格朗日反演的例题见此,附 \(3\) 也是应用拉格朗日反演证明的。
\(1.5\) 分式分解
在正式阐述分式分解的形式前,我们需要先引入一个有着良好性质的分式:
\[\frac{a}{(1 - \rho z)^{m + 1}}= \sum_{n \ge 0} \binom{m + n}{m} a\rho^n z^n\]可以采用归纳法证明,不再赘述。
一个有限个级数的和函数 \(S(z)\) 也具有良好的性质,其有着如下形式:
\[S(z) = \frac{a_1}{(1 - \rho_1 z)^{m_1 + 1}} + \frac{a_2}{(1 - \rho_2 z)^{m_2 + 1}} + \cdots + \frac{a_l}{(1 - \rho_l z)^{m_l + 1}}\]这是由于我们可以轻易地提取系数:
\[[z^n]S(z) = a_1\binom{m_1 + n}{m_1} \rho_1^n + a_2\binom{m_2 + n}{m_2} \rho_2^n + \cdots + a_l\binom{m_l + n}{m_l} \rho_l^n\]可以证明,任意 \(R(0) \neq \infty\) 的有理函数
\[R(z) = \frac{P(z)}{Q(z)}\]都可以被写成形如 \(S(z) + T(z)\) 的形式,其中 \(S(z)\) 如上定义,\(T(z)\) 是一个多项式。因此对于 \(R(z)\) 的系数总有一个封闭形式来表示。求得 \(S(z)\) 与 \(T(z)\) 等价于找到 \(R(z)\) 的“部分分式展开”。
注意到 \(T(z)\) 在 \(z \neq \infty\) 时定不为 \(0\)。因此 \(R(z) = \infty\) 的情况只能说明 \(S(z) = \infty\),即 \(z \in\{1/\rho_1 , 1/\rho_2 ,\dots, 1/\rho_l\}\) 的情况。因此如果我们想顺利地将 \(R(z)\) 表为 \(S(z) + T(z)\) 的形式,所需的每个 \(\rho_i\) 就应当分别是 \(Q(\alpha)\) 的零点 \(\alpha_i\) 的倒数。
我们假设 \(Q(z)\) 形如
\[Q(z) = q_0 + q_1z + \cdots + q_mz^m \]需要满足 \(q_0, q_m \neq 0\)。
我们定义 \(Q(z)\) 的”翻转“ \(Q^{R}(z)\) 形如
\[Q^{R}(z) = q_0 z^m + q_1z^{m-1} + \cdots + q_m\]我们可以发现 \(Q(z)\) 和它的翻转具有以下的关系:
\[\begin{aligned}Q^R(z) & = q_0 (z - \rho_1) (z - \rho_2) \cdots (z - \rho_m) \\Q(z) & = q_0 (1 - \rho_1z) (1 - \rho_2z) \cdots (1 - \rho_mz) \\\end{aligned}\]这表明一个多项式 \(Q(z)\) 的零点是它翻转的对应零点的倒数。因此,我们若想找到 \(\rho_i\),就可以将 \(Q^R(z)\) 进行分式分解。具体的应用将会在下方给出,现在首先介绍两条定理。
\(\textbf{定理 1.5.1 }\text{(不同根的有理展开定理)}\)
设 \(R(z) = P(z) / Q(z)\),其中 \(Q(z) = q_0(1 - \rho_1z) (1 - \rho_2z) \cdots (1 - \rho_lz)\)。若 \(\rho_1, \rho_2, \dots, \rho_l\) 彼此不同,且 \(P(z)\) 是一个度数小于 \(l\) 的多项式,则我们有
\[[z^n]R(z) = a_1 \rho_1^n + \cdots + a_l \rho_l^n, \qquad a_k = \frac{-\rho_k P(1 / \rho_k)}{Q"(1 / \rho_k)}\]
证明:
令 \(a_i\) 如上地定义。如果定理成立,则 \(R(z) = P(z)/Q(z)\) 应当等于
\[S(z) = \frac{a_1}{1 - \rho_1z} + \frac{a_2}{1 - \rho_2z} + \cdots + \frac{a_l}{1 - \rho_lz}\]为证明这一点,我们只需要证明 \(T(z) = R(z) - S(z)\) 在 \(z \to 1 / \rho_i\) 时不会趋向正无穷。这将表明一个分式永远不可能取得正无穷,也就是这个分式退化为了一个多项式。我们同样可以证明当 \(z \to \infty\) 时 \(T(z)\to 0\),这表明 \(T(z) = 0\)。
令 \(\alpha_i = 1 / \rho_i\)。为证明 \(\lim_{z\to \alpha_i} T(z) \neq \infty\),我们只需证明 \(\lim_{z\to \alpha_i} (z - \alpha_i)T(z) = 0\),这是由于 \(T(z)\) 是一个有理函数。我们想证明的即为
\[\lim_{z\to \alpha_i} (z - \alpha_i) R(z) = \lim_{z\to \alpha_i}(z - \alpha_i) S(z)\]等号右侧的处理是简单的。对任意 \(j \neq i\),我们有
\[\lim_{z\to \alpha_i} \frac{a_j (z - \alpha_i)}{1 - \rho_jz} = 0\]因此等号右侧只剩第 \(i\) 项,消同类项得到右侧即为 \(\dfrac{-a_i}{\rho_i} = \dfrac{P(\alpha_i)}{Q"(\alpha_i)}\)。
左侧的极限可以通过洛必达法则(定理 附 \(1.1\))求得:
\[\lim_{z \to \alpha_i} (z - \alpha_i)\frac{P(z)}{Q(z)} = P(\alpha_i)\lim_{z \to \alpha_i} \frac{z - \alpha_i}{Q(z)} = \frac{P(\alpha_i)}{Q"(\alpha_i)} \]证毕。
这样,我们就解决了 \(Q(z)\) 无重根的情况。当 \(Q(z)\) 存在重根时,计算就会变得复杂起来。但是我们仍然可以加强我们得到的结论,得到以下的一般结果:
\(\textbf{定理 1.5.2 }\text{(有理生成函数的一般展开定理 )}\)
设 \(R(z) = P(z) / Q(z)\),其中 \(Q(z) = q_0(1 - \rho_1z)^{d_1} (1 - \rho_2z)^{d_2} \cdots (1 - \rho_lz)^{d_l}\),且 \(\rho_1, \rho_2, \dots, \rho_l\) 彼此不同。若 \(P(z)\) 是一个度数小于 \(l\) 的多项式,则我们有
\[[z^n]R(z) = f_1(n) \rho_1^n + \cdots + f_l(n) \rho_l^n\]其中 \(f_k(n)\) 是一个 \(d_k - 1\) 度的多项式,其首项系数为
\[a_k = \frac{-\rho_k^{d_k} P(1/\rho_k)d_k}{Q^{(d_k)}(1 / \rho_k)} = \frac{P(1 / \rho_k)}{(d_k - 1)! q_0 \prod_{j\neq k} (1 - p_j / p_k)^{d_j}}\]
此定理可以通过在 \(\max \{d_i\}\) 上做归纳得到,需要用到
\[R(z) - \frac{a_1(d_1 - 1)!}{(1 - \rho_1z)^{d_1}} - \frac{a_2(d_2 - 1)!}{(1 - \rho_2z)^{d_2}} - \cdots - \frac{a_l(d_l - 1)!}{(1 - \rho_lz)^{d_l}}\]是一个分母多项式无法被任意 \((1 - \rho_k z)^{d_k}\) 整除的有理函数。
需要注意的是,该定理本身无法确定任意 \(f_i\) 的表示形式,需要使用待定系数法求解。
在实际应用中不好使用如上的两种做法,这里也提供一些做法以供代替使用。下面仍然定义 \(R(z) = P(z) / Q(z)\)。
第一种方法是找到一个 \((1 - z^k)^t\) 满足 \(Q(z) \mid (1 - z^k)^t\),这时我们可以将一个简单的形式放在分子上。我们记 \(A(z) = \dfrac{(1 - z^k)^t}{Q(z)}\),则 \(R(z) = \dfrac{A(z)P(z)}{(1 - z^k)^t}\)。我们应当构造尽量简单的封闭形式来表出 \(R(z)\)。
第二种方法是待定系数法,也是常见的做法。具体内容在上面的链接中有讲述。
到这里幂级数相关的知识就大致介绍完了。下面我们将介绍——
\(2.\) 生成函数(\(\underline{\textbf{G}}\text{enerating} \ \underline{\textbf{F}}\text{unction}, \ \text{GF}\))
生成函数是一种工具,就像是一个袋子。我们并不去独立地考察那些个体,那是很愚蠢的。相反,我们将它们全部放进一个袋子。这之后,我们所需要考察的对象就只有一个了——那袋子。
—— $\text{George Polya}\qquad$
\(2.1\) 定义及性质
一个无穷序列的生成函数是一个形式幂级数,每一项的系数可以提供关于这个序列每个元素的信息。生成函数的构造应当是易于在具体情况下分析序列信息的。下面具体定义:
\(\textbf{2.1.1 }\text{(生成函数)}\)
对于一个无穷数列 \(\langle a_i \rangle\),定义其关于占位元 \(k_i(x)\) 的生成函数 \(F(x)\) 如下:
\[F(x) = \sum_{i = 0}^{\infty} a_i k_i(x)\]
其中,占位元的不同取法分别对应着不同的情况,常见的例子如下:
- \(k_i(x) = x^i\)这对应着普通生成函数(\(\underline{\textbf{O}}\text{rdinary} \ \underline{\textbf{G}}\text{enerating} \ \underline{\textbf{F}}\text{unction}, \ \text{OGF}\)),其常用于组合问题。
- \(k_i(x) = \dfrac{x^i}{i!}\)这对应着指数生成函数(\(\underline{\textbf{E}}\text{xponential} \ \underline{\textbf{G}}\text{enerating} \ \underline{\textbf{F}}\text{unction}, \ \text{OGF}\)),其常用于排列问题。
- \(k_i(x) = \dfrac{1}{i^x}\)这对应着狄利克雷生成函数(\(\underline{\textbf{D}}\text{irichlet} \ \underline{\textbf{G}}\text{enerating} \ \underline{\textbf{F}}\text{unction}, \ \text{DGF}\)),其常用于元素按狄利克雷卷积贡献的问题。
我们在下面常用 \(\text{OGF}\) 作例子。
给定一个数列 \(\langle 1, 1, 1, \dots \rangle\),我们可以写出它的 \(\text{OGF } F(x)\) 如下:
\[F(x) = \sum_{i=0}^{\infty} x^i = 1 + x^2 + x^3 + \cdots\]这样,我们就将一个数列用一个函数表示出来了,在需要第 \(i\) 项时只需要提取系数即可。但我们时时都带着一个求和号运算是很不方便的,这就启发我们去寻找一个更加简便的形式表示生成函数。这个形式常被称作封闭形式。一个生成函数的封闭形式有时不唯一,你可以把简明地表述这个数列的任意形式叫做封闭形式。注意:考虑生成函数的“函数值”是完全无意义的,我们只关心生成函数每一项对应的系数,以及数列在幂级数形式下表现的性质。
例如 \(F(x) = 1 + x^2 + x^3 + \cdots\) 满足 \(F(x) = xF(x) + 1\),因此 \(F(x)\) 的封闭形式为 \(\dfrac{1}{1 - x}\)。
数列 \(1, p, p^2, \dots\) 的 \(\text{OGF}\) \(F(x) = \sum_{i=0}^{\infty} (px)^i\) 的封闭形式也可以类似地导出,是 \(\dfrac {1}{1 - px}\)。
\(2.2\) 常用的形式操作和 \(\text{OGF}\)
下面我们将采用生成函数法求解一些经典问题。
\(2.3\) 例题
\(2.3.1\):找零问题
你有无穷多的 \(1\) 元、\(2\) 元和 \(5\) 元的硬币。你需要支付 \(n\) 元,请问有多少种方案。
我们设 \(F[n] =\) 支付 \(n\) 元的方案数。特殊的,\(F[0] = 1\)。
我们用 \(\langle 1\rangle\)、\(\langle 2\rangle\) 与 \(\langle 5\rangle\) 分别表示三种面值的硬币。我们定义一种支付方案为一组硬币的组合。若一组硬币有 \(a\) 个 \(\langle 1\rangle\)、\(b\) 个 \(\langle 2\rangle\)、\(c\) 个 \(\langle 5\rangle\),则记作 \(\langle 1\rangle^a \langle 2\rangle^b \langle 5\rangle^c\)。一种支付方案的价值记为这种方案内硬币的价值总和,记作 \(value\left(\langle 1\rangle^a \langle 2\rangle^b \langle 5\rangle^c\right) = a + 2b + 5c\)。
定义两种支付方案 \(S_1, S_2\) 的乘法表示这两种支付方案同时支付。这样定义,任意硬币在 \(S_1\times S_2\) 中被使用的次数是两边对应硬币幂次之和,这符合我们对幂的认知。同时 \(value(S_1\times S_2) = value(S_1) + value(S_2)\)。
定义两种支付方案 \(S_1, S_2\) 的加法表示这两种方案的并列。容易验证乘法对加法有分配律。
我们采用无穷求和来表示所有可能的支付方式的并列。
假设我们只能支付 \(1\) 元的硬币,则所有可能的支付方案可以表示为
\[P_{\{1\}} = \varnothing + \langle 1 \rangle + \langle 1 \rangle^3 + \langle 1 \rangle^3 + \cdots = \frac{1}{1 - \langle 1 \rangle}\]注意,我们并不考虑带入一个值后的实际意义,这只是表述支付方案的封闭形式。
随后我们加入 \(2\) 元的硬币。这表示我们能够在每种方案中加入任意数量的 \(\langle 2 \rangle\)。这时的支付方案可以表示为
\[P_{\{1,2\}} = \varnothing P_{\{1\}} + \langle 2 \rangle P_{\{1\}} + \langle 2 \rangle^3 P_{\{1\}} + \langle 2 \rangle^3 P_{\{1\}} + \cdots = \left(\varnothing + \langle 2 \rangle + \langle 2 \rangle^3 + \langle 2 \rangle^3 + \cdots\right) P_{\{1\}} = \frac{1}{1 - \langle 1 \rangle} \frac{1}{1 - \langle 2 \rangle}\]类似地,我们能得到加入 \(5\) 元硬币的答案:
\[P_{\{1,2,5\}} = \frac{1}{1 - \langle 1 \rangle} \frac{1}{1 - \langle 2 \rangle}\frac{1}{1 - \langle 5 \rangle}\]需要注意的是,\(P_{\{1,2,5\}} \neq \sum_{k \ge 0}(\langle 1 \rangle + \langle 2 \rangle + \langle 5 \rangle)^k\)。
若我们只关心总面值,则可以记 \(z^k\) 为一种面值和为 \(k\) 的方案,则 \(\langle 1 \rangle = z^1, \langle 2 \rangle = z^2, \langle 5\rangle = z^5\)。我们的答案即为
\[[z^n]\frac{1}{1 - z} \frac{1}{1 - z^2}\frac{1}{1 - z^5}\]具体表出答案将用到分式分解的知识,留作读者练习。
\(2.3.2\):斐波那契数列
首先需要对斐波那契数列进行定义。斐波那契数列是一个无穷数列 \(\langle f_i \rangle\),满足
\[f_0 = 0,\quad f_1 = 1,\quad f_n = f_{n - 1} + f_{n - 2}\ (i > 1)\]考虑斐波那契数列的 \(\text{OGF}\),记作 \(F(x)\)。我们可以通过平移、按比例增加生成函数系数的变换,使得一系列变换后的生成函数的任意一位可以通过原递归式表示变换前的生成函数对应的一位。以本生成函数为例。
\[\begin{aligned}F(x) &= &f_0\ +\ &f_1x\ + &f_2x^2 + f_3x^3 + \cdots \\ xF(x) &= &\quad &f_0x\ + &f_1x^2 + f_2x^3 + \cdots \\x^2F(x) &= &\quad &\quad & f_0x^2 + f_1x^3 + \cdots \\\end{aligned}\]可以发现,\(xF(x) + x^2F(x)\) 的系数正好表示出了 \(F(x)\) 次数大于 \(1\) 部分的系数。也就是说,\(F(x)\) 满足
\[F(x) = x + xF(x) + x^2 F(x)\]等号右侧加入的 \(x\) 是修正系数用的。
不难从如上的关系式中推得 \(F(x)\) 的封闭形式
\[F(x) = \frac{x}{1 - x - x^2}\]然而目前而言,这个封闭形式并未给我们提供有用的信息,还需要进一步地转换。举个例子,我们想求得 \(f_n\) 仅使用 \(n\) 的表示法,即直接提取 \(F(x)\) 的第 \(n\) 项系数。这里我们仍然可以采用分式分解中的待定系数法。
具体地,我们首先计算分母的因式分解,随后设未知数使 \(F(x)\) 被表示为两个简单分式的和的形式,最后平凡地提取系数。
我们可以解得 \(1 - x - x^2 = 0\) 的两个根 \(x_1 = \dfrac{-1 + \sqrt 5}{2}, x_2 = \dfrac{-1 - \sqrt 5}{2}\)。随后 \(F(x)\) 的分母就是 \((x - x_1)(x - x_2)\) 了。
随后我们设
\[F(x) = \frac{a}{x - x_1} + \frac{b}{x - x_2}\]这直接给出了方程组
\[\left\{\begin{aligned}&a + b = 1\\&ax_1 + bx_2 = 0\end{aligned}\right.\]解得 \(a = \dfrac{5 + \sqrt 5}{10}, b = \dfrac{5 - \sqrt 5}{10}\)。随后提取系数:
\[\begin{aligned}[x^n] F(x) & = [x^n]\frac{x}{1 - x - x^2}\\ & = [x^n]\left(\frac{a}{x - x_1} + \frac{b}{x - x_2}\right)\\ & = [x^n]\left(\frac{- a / x_1}{1 - x / x_1} + \frac{- b / x_2}{1 - x / x_2}\right)\\ & = -\left(\frac{a}{x_1^{n + 1}} + \frac{b}{x_2^{n + 1}}\right)\end{aligned}\]带入即可得到
\[f_n = \frac{\sqrt 5}{5} \left(\left(\frac{1 + \sqrt 5}{2}\right) ^ n - \left(\frac{1 - \sqrt 5}{2}\right) ^ n\right)\]此处同样可以应用不同根的有理展开定理。对比 \(R(z)\) 的表达式可以发现 \(P(z) = z, Q(z) = 1 - z - z^2 = (1 - \phi z)(1 - \hat\phi z)\),其中 \(\phi,\hat\phi\) 为 \(Q^R(z) = z^2 - z - 1\) 的两个根。容易得到 \(Q"(z) = -1 - 2z\),
\[\frac{-\rho P(1 / \rho)}{Q"(1 / \rho)} = \frac{-\rho (1 / \rho)}{-1 - 2 / \rho} = \frac{-1}{-1 - 2 / \rho} = \frac{\rho}{\rho + 2}\]根据定理 \(1.5.1\),\(\phi\) 的系数就应当是 \(\dfrac{\phi}{\phi + 2} = \dfrac{1}{\sqrt 5}\),而 \(\hat\phi\) 的系数是 \(\dfrac{\hat\phi}{\hat\phi + 2} = \dfrac{-1}{\sqrt 5}\)。带入得到
\[f_n = \frac{\phi^n + \hat\phi^n}{\sqrt 5} = \frac{\sqrt 5}{5} \left(\left(\frac{1 + \sqrt 5}{2}\right) ^ n - \left(\frac{1 - \sqrt 5}{2}\right) ^ n\right)\]\(2.3.3\):卡特兰数
我们定义卡特兰数 \(Cat(i)\) 如下:\(Cat(0) = 1, Cat(n) = n\) 对括号匹配合法的序列数。
想要通过生成函数刻画一个组合对象,一个经典的思路就是首先得到递推式,随后使用生成函数刻画对应的递推式,得到递归构造,最终解出封闭形式或采用牛顿迭代法求解。在本题中也不例外,我们首先寻找卡特兰数满足的递推式。寻找递推式的过程应当具体地结合组合对象自己的性质,这点是无法总结归纳的。在本题中,我们可以枚举新一对括号内的子括号序列,并在其外面放置合法的括号序列。这也得到了
\[Cat(n + 1) = \sum_{i=0}^n Cat(i)\times Cat(n - i)\]构造卡特兰数的 \(\text{OGF } C(z)\)。可以发现上式右侧是 \(Cat(n + 1) = [z^n]C^2(z)\)。这里考虑 \(Cat(n + 1)\) 的 \(\text{OGF}\)。容易发现其就是将零次项改为 \(0\) 后系数左移。也就是
\[\frac{C(z) - 1}{z} = C^2(z)\]这自然地导出了 \(C(z)\) 的封闭形式:
\[C(z) = \frac{1 \pm\sqrt{1 - 4z}}{2z}\]这里发现出现了两个根,我们要讨论根的取舍问题。然而由于数列是存在的,因此必有一根可以取到,我们只需要判断哪个根满足显然的性质即可。考虑 \(C(0) = [z^0]C(z) = 1\),而 \(+\) 的情况取到正无穷,不满足该性质,因此我们得到了
\[C(z) = \frac{1 - \sqrt{1 - 4z}}{2z}\]得到了封闭形式后提取系数就变得简便了。我们可以直接应用广义二项式定理,得到
\[(1 - 4z)^{1/2} = \sum_{i=0}^{\infty}\binom{1/2}{i}(-4z)^i = 1 + \sum_{i=1}^{\infty}\binom{1/2}{i}(-4z)^i\]\[\begin{aligned}C(z) & = \frac{1 - \sqrt{1 - 4z}}{2z}\\ & = \frac{1}{2z} \left(1 - 1 - \sum_{i=1}^{\infty}\binom{1/2}{i}(-4z)^i\right)\\ & = - \frac{1}{2z} \left(\sum_{i=1}^{\infty}\binom{1/2}{i}(-4z)^i\right)\\ & = 2 \sum_{i=1}^{\infty}\binom{1/2}{i}(-4z)^{i-1}\\ & = 2 \sum_{i=1}^{\infty}\frac{(1 / 2)^{\underline i}}{i!}(-4z)^{i-1}\\ & = 2 \sum_{i=1}^{\infty}\frac{(1/2)(-1/2)(-3/2)\cdots(3/2-i)}{i!}(-4z)^{i-1}\\ & = 2 \sum_{i=1}^{\infty}\frac{(1/2)(1/2)(3/2)\cdots(i - 3/2)}{i!}(4z)^{i-1}\\ & = \sum_{i=1}^{\infty}\frac{(1/2)(3/2)\cdots(i - 3/2)}{i!}(4z)^{i-1}\\ & = \sum_{i=1}^{\infty}\frac{(2i-3)!!}{i!}(2z)^{i-1}\\ & = \sum_{i=1}^{\infty}\frac{(2i-2)!}{i!(i-1)!}z^{i-1}\\ & = \sum_{i=1}^{\infty}\frac{(2i)!}{i!(i+1)!}z^i\\ & = \sum_{i=1}^{\infty}\frac{1}{i+ 1}\binom{2i}{i}z^i\end{aligned}\]这就得到了卡特兰数的经典形式。
\(2.4\) 简析生成函数
\(2.4.1 \text{ OGF}\)
\(\text{OGF}\) 正如它的名字,是最简单的构造一个序列的生成函数的方法,我们将每个元素加入以编号为幂次的占位元来区分每个元素。两个 \(\text{OGF}\) 的乘法是经典的加卷积。
两个 \(\text{OGF}\) 之间的运算有着一系列的组合意义。加法:在生成函数意义上,两个 \(\text{OGF}\) 的对应位置的值相加,这表示着不相交的两个集合的并。乘法:两个 \(\text{OGF}\) 对应位置代表着两个集合,而乘法就产生了这两个集合的笛卡尔积,即在这两个集合中分别选出一个组成二元组的全体对应的集合。
我们可以发现,\(\text{OGF}\) 的乘法和计数背包的合并是同构的。这也表明了 \(\text{OGF}\) 在处理组合问题上的代数意义。
常见的 \(\text{OGF}\) 形式已于上方列出。
\(2.4.2 \text{ EGF}\)
考察 \(e^x\) 的麦克劳林级数形式,我们能够发现 \(\text{EGF}\) 得名的原因。同时,这个形式也为其处理排列问题提供了方便,因为其卷积能自然地拼凑出组合数的形式。如下:
\[(F\times G)(x) = \sum_{k\ge 0} \sum_{i + j = k} \frac{F[i]x^i}{i!} \frac{G[j]x^j}{j!} = \sum_{k\ge 0} \sum_{i + j = k} \binom{k}{i} F[i] G[j] \frac{x^k}{k!} \]这也表明了为何 \(\text{EGF}\) 更加适合应用于有标号有顺序对象的组合问题。首先可以发现,一组标号给一组对象只能产生一种情况,因为我们需要保证标号是有序的。我们需要从这 \(i + j\) 个标号中选择 \(i\) 个标号给前一部分元素,因此得到一个系数 \(C_k^i\)。
两个 \(\text{EGF}\) 之间的运算有着一系列的组合意义。加法仍然和 \(\text{OGF}\) 相同,是不相交集合的并。乘法:在上面已经阐述,我们产生两个集合的笛卡尔积时,应当考虑一次产生会出现多少不同标号的集合,将这一值作为系数加入乘积对应项。这也就是有标号对象对应集合的笛卡尔积。
在这里需要介绍多项式指数函数施在 \(\text{EGF}\) 上的组合意义。我们取一个 \(\text{EGF } F(x)\),其描述了一种有标号的组合元素,则 \(\exp F(x)\) 就描述了由这种组合元素构成的有标号集合的方案数。有兴趣进一步了解的可以参阅 OI-Wiki 对这部分内容的讲解。
一些常见的 \(\text{EGF}\) 形式:
\[\begin{aligned}\langle 1, 1, 1, 1, 1, \cdots\rangle \qquad & \to \quad& &e^x \\\langle 1, -1, 1, -1, 1, \cdots\rangle \qquad & \to \quad & &e^{-x} \\\langle 1, 0, 1, 0, 1, \cdots\rangle \qquad & \to \quad & &\frac{e^x + e^{-x}}{2} \\\langle 1, c, c^2, c^3, c^4, \cdots\rangle \qquad & \to \quad & &e^{cx} \\\langle 1, a, a^{\underline 2}, a^{\underline 3}, a^{\underline 4}, \cdots\rangle \qquad & \to \quad & &(1 + x)^a\end{aligned}\]实现时处理 \(\text{EGF}\) 常将 \(x^k\) 和 \(1/k!\) 分开,后者作为 \(x^k\) 系数的一部分储存。因此在提取 \([x^n/n!]\) 项系数时应当改作提取 \([x^n]\) 项系数的 \(n!\) 倍。
\(2.4.3 \text{ DGF}\)
\(\text{DGF}\) 的特殊构造和其名字有着密不可分的联系。也就是说,其是被专门构造来处理数论函数的。
两个 \(\text{DGF}\) 之间的乘法有着一系列的数论意义。我们能看到,两个数论函数的 \(\text{DGF}\) 的乘积是两者的狄利克雷卷积对应的 \(\text{DGF}\)。
\[(F\times G)(z) = \sum_{i\ge 1}\sum_{j \ge 1} \frac{F[i]}{i^z} \frac{G[j]}{j^z} = \sum_{i\ge 1}\sum_{j \ge 1} \frac{F[i]G[j]}{(ij)^z} = \sum_{i\ge 1}\left(\sum_{d|i} F[d]G\left[\frac{i}{d}\right]\right)\frac{1}{i^x}\]如果一个 \(\text{DGF } F(x)\) 对应着一个积性函数 \(f(n)\),则该 \(\text{DGF}\) 可以被 \(f\) 在质数幂次处的取值表示。记 \(\mathbb P\) 为质数集合,我们有
\[F(x) = \prod_{p\in \mathbb P} \left(1 + \frac{f(p)}{p^x} + \frac{f(p^2)}{p^{2x}} + \frac{f(p^3)}{p^{3x}} \cdots\right)\]可以应用它证明一些结论,或是构造一些筛法的函数。相关的应用可以类比贝尔级数。
附录
附 \(1.\) 经典微积分
请自行阅读《高等数学(上册)》获得必要知识,这里只作列出。
\(\textbf{定义 1.1 } \text{(求导) }\)
定义对函数 \(f(x)\) 的形式导数 \(f"(x)\) 满足 \([x^{k-1}] f"(x) = k f[k]\)。
下面 \(f, g\) 都是以 \(x\) 为自变量的一元函数,\(c\) 为常数。
\[(cf)" = cf" \quad (f + g)" = f" + g" \quad (f - g)" = f" - g" \quad (fg)" = f"g + g"f \quad (f/g)" = \frac{f"g - g"f}{g^2}\]\[c" = 0 \quad (x^k)" = kx^{k-1} \quad (a^x)" = a^x \ln a \quad (\log_a x)" = \frac{1}{x\ln a}\]\[(\sin x)" = \cos x \quad (\cos x)" = - \sin x \quad (\tan x)" = \sec^2 x \]\[(\sec x)" = \sec x\tan x \quad (\csc x)" = - \csc x \cot x \quad(\cot x)" = -\csc^2 x \]\[f(g(x)) = g"(x) f"(g(x))\quad \left(f^{\langle -1\rangle}\right)" = 1 / f"\]记对 \(f(x)\) 求 \(k\) 次导数得到的值为 \(f^{(k)}(x)\)。
\[(fg)^{(k)} = \sum_{i = 0}^k\binom{k}{i} f^{(i)} g^{(k-i)}\]记函数 \(f(x, y)\) 对 \(x\) 求偏导为 \(\frac{\text d}{\text d x} f(x)\).
\[\frac{\text d u}{\text d y} \frac{\text d y}{\text d x} = \frac{\text d u}{\text d x}\]求导是操作系数的一个经典方法,因此定义如下的算子:
\(\textbf{定义 1.2 } \text{(}\vartheta\text{ 算子) }\)
对一个函数 \(f(x)\) 定义 \(\vartheta\) 算子 \(\vartheta f(x)\):
\[\vartheta f(x) = x f"(x)\]可以发现 \([x^k]\vartheta f(x) = kf[k]\)。需要注意的是,\(0\) 次项可能需要重新定义。
积分和求导同样重要。
\(\textbf{定义 1.3 } \text{(积分) }\)
定义对函数 \(f(x)\) 的形式积分操作 \(\int f(x)\) 满足 \([x^{k+1}] \int f(x) = f[k] / (k + 1)\)。
下面 \(f, g\) 都是以 \(x\) 为自变量的一元函数,\(c\) 为常数。
\[\int (f \pm g) \text dx = \int f(x) \text dx \pm \int g(x) \text dx \quad \int cf(x) \text dx = c\int f(x) \text dx\]\[\int g"(f(x)) f"(x) \text dx = g(f(x)) + c \quad (第一类换元法原理)\]\[\int f"(x)g(x) \text dx = f(x)g(x) - \int f(x)g"(x)\text dx \quad (分部积分法原理)\]\(\textbf{定理 附 1.1 } \text{(洛必达法则) }\)
若函数 \(f(x), g(x)\) 满足如下条件:
\[\lim_{x \to a} \frac{f(x)}{g(x)} = \lim_{x \to a} \frac{f"(x)}{g"(x)} = A\]
- \(\lim\limits_{x \to a} f(x) = 0, \ \lim\limits_{x \to a} g(x) = 0\)
- \(f,g\) 在点 \(a\) 的某一去心邻域内可导,且 \(g"(x)\neq 0\)。
- \(\lim\limits_{x \to a} \dfrac{f"(x)}{g"(x)} = A\),其中 \(A \in \mathbb R\) 或 \(A = \pm \infty\)。则我们有
附 \(2.\) 离散微积分
类比经典微分算子 \(\text d\) 取到无穷小的操作,这里定义差分算子取到离散情况的最小:\(1\)。当然我们也需要定义点值平移的算子。
\(\textbf{定义 附 2.1 }\text{(差分算子 }\Delta\text { )}\)
对于一个函数 \(f\),我们定义 \(\Delta f(x) = f(x + 1) - f(x)\)。
经典微分中存在 \(\text d e^x = e^x\),而在这里存在 \(\Delta 2^n = 2^n\)。
\(\textbf{定义 附 2.2 }\text{(平移算子 E )}\)
对于一个函数 \(f\),我们定义 \(\text E f(x) = f(x + 1)\)。\(\Delta = \text E - 1\)。
众所周知,\(\text d x^n = n x^{n-1}\)。那么在离散微积分中有没有类似的函数呢?是有的。我们接下来就将阐述这种函数:
\(\textbf{定义 附 2.3 }\text{(阶乘幂) }\)
阶乘幂分为下降幂和上升幂。
- 下降幂 \(x^{\underline n} = x(x - 1)(x - 2)\cdots (x - n + 1)\)。当 \(n > 0, -n < 0\) 的时候,有 \(x^{\underline{-n}} = \frac{1}{(x + 1)(x + 2)\cdots (x + n)}\)。\(x^{\underline{a + b}} = x^{\underline a}(x - a)^{\underline b}\)
- 上升幂 \(x^{\overline n} = x(x + 1)(x + 2)\cdots (x + n - 1)\)。当 \(n > 0, -n < 0\) 的时候,有 \(x^{\overline{-n}} = \frac{1}{(x - 1)(x - 2)\cdots (x - n)}\)。\(x^{\overline{a + b}} = x^{\overline a}(x + a)^{\overline b}\)\(x^{\underline n} = (-1)^n (- x)^{\overline n}\)
可以发现,\(\Delta x^{\underline n} = n x^{\underline {n-1}}\)。
类比经典不定积分算子 \(\int\),我们也可以对微分算子求和,得到有限积分算子(通常求和 \([0, n)\))。
有:
\[\int x^k = \frac{x^{k + 1}}{k + 1} \Rightarrow \sum_{i=0}^{n-1} i^k = \frac{n^{\underline{k + 1}}}{k + 1} \]\[\int \frac 1x = \ln x \Rightarrow \sum_{i=0}^{n-1} i^{\underline {-1}} = \sum_{i=1}^{n} \frac 1i = H_n \]附 \(3.\) 一些具体的级数
在推导的过程中可以发现,这两种广义级数对应的定理从证明方法到具体步骤都是很相似的,同时两者之间也有着不小的联系。
参考资料:
广义二项/指数级数, qwaszx《具体数学》
\(3.1\) 广义二项级数
\(\textbf{定义 附 3.1.1 }\text{(广义二项级数)}\)
定义广义二项级数为
\[\mathcal{B}_t(z) = \sum_{n \ge 0} \binom{tn + 1}{n} \frac{z^n}{tn + 1} = \sum_{n\ge 0}(tn)^{\underline{n-1}} \frac{z^n}{n!}\]
我们首先需要得到其封闭形式。这就需要我们证明如下的定理:
\(\textbf{定理 附 3.1.1 }\text{(封闭形式)}\)
广义二项级数满足
\[\mathcal{B}_t(z) = z\mathcal{B}_t(z)^t + 1\]
证明:
令 \(F(z) = \mathcal{B}_t(z) - 1\),这就得到
\[F(z) = z(F(z) + 1)^t\]这个形式容易构造 \(G(z) = F^{\langle -1\rangle} = \dfrac{z}{(1 + z)^t}\)。应用定理 \(1.4.2\) 得到
\[[z^n]F(z) = \frac 1n [z^{n-1}] \left(\frac{z}{G(z)}\right)^n = \frac 1n [z^{n-1}](1 + z)^{nt} = \frac 1n \binom{nt}{n-1}\]\(n > 0\) 时应用吸收恒等式得到
\[\frac 1n \binom{nt}{n-1} = \frac{1}{nt + 1}\binom{nt + 1}{n}\]\(n = 0\) 时显然成立。
因此得到了如此构造的 \(\mathcal{B}_t(z)\) 满足定义式。
证毕。
有时我们会发现这个形式并不广泛,这就启发我们构造一些更广泛的形式,如下。
\(\textbf{定理 附 3.1.2 }\)
广义二项级数满足
\[\mathcal{B}_t(z)^r = \sum_{n \ge 0} \binom{tn + r}{n} \frac{r}{tn + r}z^n\]
证明:
令 \(H(z) = (z + 1)^r\),应用定理 \(1.4.2\) 得到
\[[z^n]\mathcal{B}_t(z)^r = [z^n]H(F(z)) = \frac{1}{n} [z^{n-1}] H"(z) \left(\frac{z}{G(z)}\right)^n = \frac{r}{n} [z^{n-1}](1 + z)^{nt + r - 1} = \frac{r}{n} \binom{nt + r - 1}{n - 1}\]如上地讨论可以得到 \(\mathcal{B}_t(z)^r\) 的系数满足定理。
证毕。
然后我们需要证明一个虽然有用但是证明十分麻烦的定理。
\(\textbf{定理 附 3.1.3 }\)
广义二项级数满足
\[\frac{\mathcal{B}_t(z)^r}{ 1 - t + t\mathcal{B}_t(z)^{-1}} = \sum_{n \ge 0} \binom{tn + r}{n}z^n\]
令 \(H(z) = \dfrac{(1 + z)^r}{1 - t + t(1 + z)^{-1}}\)。应用定理 \(1.4.2\) 得到
\[\begin{aligned}& [z^n]\frac{\mathcal{B}_t(z)^r}{ 1 - t + t\mathcal{B}_t(z)^{-1}}\\ = \ & [z^n] H(F(z))\\ = \ & \frac 1n [z^{n-1}] H"(z) \left(\frac{z}{G(z)}\right)^n\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt} \left(\frac{(1 + z)^r}{1 - t + t(1 + z)^{-1}}\right)"\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt} \left(\frac{r(1 + z)^{r-1}\left(1 - t + t(1 + z)^{-1}\right) - (1 + z)^r\left(1 - t + t(1 + z)^{-1}\right)"}{\left(1 - t + t(1 + z)^{-1}\right)^2}\right)\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt} \left(\frac{r(1 + z)^{r-1}\left(1 - t + t(1 + z)^{-1}\right) + t(1 + z)^r(1 + z)^{-2}}{\left(1 - t + t(1 + z)^{-1}\right)^2}\right)\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt + r} \left(\frac{r(1 + z)^{-1}\left(1 - t + t(1 + z)^{-1}\right) + t(1 + z)^{-2}}{\left(1 - t + t(1 + z)^{-1}\right)^2}\right)\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt + r} \left(\frac{r(1 + z)^{-1}}{\left(1 - t + t(1 + z)^{-1}\right)} + \frac{t(1 + z)^{-2}}{\left(1 - t + t(1 + z)^{-1}\right)^2}\right)\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt + r} \left(\frac{r}{(1 - t)(1 + z) + t} + \frac{t}{\left((1 - t)(1 + z) + t\right)^2}\right)\\ = \ & \frac 1n [z^{n-1}] (1 + z)^{nt + r} \left(\frac{r}{1 - (t - 1)z} + \frac{t}{\left(1 - (t - 1)z\right)^2}\right)\\ = \ & \frac 1n \sum_{i=0}^{n-1} \binom{nt + r}{i} \left(r(t - 1)^{n - 1 - i} + t(n - i)(t - 1)^{n - 1 - i}\right) \\ = \ & \frac 1n \left((nt + r)\sum_{i=0}^{n-1} \binom{nt + r}{i} (t - 1)^{n - 1 - i} - t\sum_{i=0}^{n-1} \binom{nt + r}{i} i(t - 1)^{n - 1 - i}\right) \\ = \ & \frac 1n [z^{n-1}]\left((nt + r)\frac{(1 + z)^{nt + r}}{1 - (t - 1)z} - t\frac{z\left((1 + z)^{nt + r}\right)"}{1 - (t-1)z}\right)\\ = \ & \frac 1n [z^{n-1}]\frac{(nt + r)(1 + z)^{nt + r} - tz(nt + r)(1 + z)^{nt+r-1}}{1 - (t - 1)z} \\ = \ & \frac 1n [z^{n-1}]\frac{(nt + r)(1 + z)^{nt + r - 1} (1 - z - tz)}{1 - (t - 1)z} \\ = \ & \frac 1n [z^{n-1}](nt + r)(1 + z)^{nt + r - 1}\\ = \ & \frac {nt + r}n \binom{nt + r - 1}{n-1}\\ = \ & \binom{nt + r }{n}\end{aligned}\]证毕。
发生了严重的中间表示膨胀神乎其技
中间由生成函数形式转化为系数形式再转化为生成函数形式的手法来自 营业日志 2020.5.9, EntropyIncreaser。这个手法常用在被提取级数形式简单但无法进一步化简的情况。感觉直接在生成函数上推导的方式是可以试着从结果倒着推导出来的,但未成功。
关于这些定理的组合意义证明可以参考《具体数学》\(7.5\) 章例 \(5\)。
这里提一句,\(\mathcal{B}_2(z)\) 的系数又称卡特兰数。
\(\text{Bonus :}\)(具体数学 习题 \(5.19\))如何证明 \(\mathcal{B}_t(z)\times \mathcal{B}_{1 - t}(-z) = 1\)?
\(3.2\) 广义指数级数
\(\textbf{定义 附 3.2.1 }\text{(广义指数级数)}\)
定义广义指数级数为
\[\mathcal{E}_t(z) = \sum_{n \ge 0} {(nt + 1)}^{n-1}\frac{z^n}{n!}\]
下面仍然是三个和上面类似的定理。
\(\textbf{定理 附 3.2.1 }\)
广义指数级数满足
\[\mathcal{E}_t(z)^{-t} \ln \mathcal{E}_t(z) = z\]
令 \(F(z) = \ln \mathcal{E}_t(z)\),则有
\[\frac{F(z)}{e^{tF(z)}} = z\]我们现在需要验证满足上面的 \(F(z)\) 对应的 \(e^{F(z)}\) 的系数是否即为 \(\mathcal{E}_t(z)\) 的系数。由上式可以发现 \(F^{\langle -1\rangle}(z) = \dfrac{z}{e^{tz}}\)。应用定理 \(1.4.2\) 得到
\[[z^n] e^{F(z)} = \frac 1n [z^{n-1}] \left(e^ z\right)"\left(\frac{z}{F^{\langle -1\rangle}(z)}\right)^n = \frac 1n [z^{n-1}] e ^{(nt + 1)z} = \frac{(nt + 1)^{n-1}}{n!} \]证毕。
\(\textbf{定理 附 3.2.2 }\)
广义指数级数满足
\[\mathcal{E}_t(z)^r = \sum_{n \ge 0} r {(tn + r)}^{n-1}\frac{z^n}{n!}\]
我们需要提取 \(e^{rF(z)}\) 的系数。由于我们已经得到了 \(F^{\langle -1\rangle}(z)\),直接应用定理 \(1.4.2\) 得到
\[[z^n] e^{rF(z)} = \frac 1n [z^{n-1}] (e^{rz})" (e^{tz})^n = \frac{r}{n} [z^{n-1}] e^{(nt + r)z} = \frac{r(nt + r)^{n-1}}{n!} \]具体数学 p.364 写到,这个定理可以通过将 \(\mathcal{E}_t(z)^r\) 视作 \(\mathcal{B}_t(z)\) 的极限情况来证明,因为不难证明
\[\mathcal{E}_t(z)^r = \lim_{x\to \infty}B_{xt}(z/x)^{xr}\]这个证明不难。先不考虑 \(r\) 次幂,写出
\[\begin{aligned}& \ \lim_{x\to \infty}B_{xt}(z/x)^{x}\\ = \ & \lim_{x \to \infty} \sum_{n \ge 0} \binom{xtn + x}{n} \frac{x}{xtn + x} \frac{z^n}{x^n}\\ = \ & \sum_{n \ge 0} \lim_{x \to \infty} \binom{x(nt + 1)}{n} \frac{z^n}{x^n(nt + 1)}\\ = \ & \sum_{n \ge 0} \left( \lim_{x \to \infty} (x(nt+1))^{\underline n} \frac{1}{x^n (nt + 1)} \right) \frac{z^n}{n!}\\ = \ & \sum_{n \ge 0} \left( \lim_{x \to \infty} (nt + 1 - 1/x)(nt + 1 - 2/x)\cdots(nt + 1 - (n - 1) / x) \right) \frac{z^n}{n!}\\ = \ & \sum_{n \ge 0} (nt + 1)^{n-1} \frac{z^n}{n!}\\ = \ & \mathcal{E}_t(z)\end{aligned}\]证毕。
\(\textbf{定理 附 3.2.3 }\)
广义指数级数满足
\[\frac{\mathcal{E}_t(z)^r}{1 - zt\mathcal{E}_t(z)^t} = \sum_{n\ge 0} (tn + r)^n \frac{z^n}{n!}\]
由定理 附 \(3.2.1\) 可以得到 \(F(z) = z\mathcal{E}_t(z)^t\)。于是我们仍然可以直接应用定理 \(1.4.2\) 得到
\[\begin{aligned}& [z^n]\frac{\mathcal{E}_t(z)^r}{1 - zt\mathcal{E}_t(z)^t}\\ = \ & \frac 1n [z^{n-1}] \left(\frac{e^{rz}}{1 - tz}\right)" (e^{tz})^n\\ = \ & \frac 1n [z^{n-1}] (e^{tz})^n \left(\frac{re^{rz}(1 - tz) + te^{rz}}{(1 - tz)^2}\right)\\ = \ & \frac 1n [z^{n-1}] e^{(nt + r)z} \left(\frac{r}{(1 - tz)} + \frac{t}{(1 - tz)^2}\right)\\ = \ & \frac 1n \left(\sum_{i=0}^{n-1} \frac{(nt + r)^i}{i!} \times rt^{n - 1 - i} + \sum_{i=0}^{n-1} \frac{(nt + r)^i}{i!} \times (n - i)t^{n - i}\right)\\ = \ & \frac 1n \left(\sum_{i=0}^{n-1} \frac{(nt + r)^i}{i!} \times t^{n - 1 - i} \times(nt + r - it) \right)\\ = \ & \frac 1n [z^{n-1}] \left((nt + r) \frac{e^{(nt + r)z}}{1 - tz} - t\frac{z(e^{(nt + r)z})"}{1 - tz}\right)\\ = \ & \frac 1n [z^{n-1}] \frac{(nt + r)e^{(nt + r)z} - tz(e^{(nt + r)z})"}{1 - tz}\\ = \ & \frac 1n [z^{n-1}] \frac{(nt + r)e^{(nt + r)z} - tz(nt + r)e^{(nt + r)z}}{1 - tz}\\ = \ & \frac 1n [z^{n-1}] \frac{(nt + r)e^{(nt + r)z} (1 - tz)}{1 - tz}\\ = \ & \frac 1n [z^{n-1}] (nt + r)e^{(nt + r)z}\\ = \ & \frac {nt + r}{n} \frac{(nt + r)^{n-1}}{(n-1)!}\\ = \ & \frac{(nt + r)^n}{n!}\end{aligned}\]证毕。
-
hive调优之参数设置
一、使用spark引擎 0、HiveonSparkhttps: www cnblogs com lq0310 p 9855245 html 1、spark资源申请set
来源: -
【速看料】IM通讯协议专题学习(七):手把手教你如何在NodeJS中从零使用Protobuf
现在随着WebSocket协议的越来越成熟,浏览器支持的越来越好,Web端的即时通讯应用也逐渐拥有了真正的“...
来源: 每日快看:浅谈多项式与生成函数
hive调优之参数设置
如何接入畅联云平台管理物联网设备?
【速看料】IM通讯协议专题学习(七):手把手教你如何在NodeJS中从零使用Protobuf
荣耀Magic 5系列镜头模组曝光:经典圆形设计、配100X长焦
每日观点:地表最快!realme宣布首发量产240W满级秒充:充满不到10分钟
李国庆称腾讯京东有大公司病 当当就是失败的案例
98年哥哥返乡给15个弟妹买一车礼物:塞满整个后备箱
荣耀MagicOS获新浪2022科技风云榜年度智能操作系统奖
统计B站番剧真实评分
基础可视化图表之分组条形图
锐龙9 6900HX加持!魔方M600迷你主机图赏
【世界报资讯】便宜还好用:绿联iPhone全系钢化膜冲量3.6元/张
世界速看:折叠屏我只认OPPO Find N2:安卓阵营独一无二
环球聚焦:宝马展示i Vision Dee概念汽车:可变换车身颜色 有科幻味了
全球视点!员工:不怕大家拿任何手机跟一加11比精致度和质感
天天消息!RHEL/CentOS yum 源问题
记 对接拼多多官方代报 辽宁电子口岸联达通客户端 ic卡加签版
天天视讯!透过现象看本质,我找到了Netty粘包与半包的这几种解决方案。
天天快资讯丨天府可乐因破产传闻销量暴增 民族品牌不会轻易垮:请理性消费
144MB暴力缓存!AMD锐龙7000 3D缓存版杀来:16核心神奇120W
马斯克最“惨” 福布斯:2022年美国亿万富翁身价创纪录暴跌
全球即时看!独立包装、现货速发:掌护快速检测试剂盒2.9元/份
世界微头条丨李斌发蔚来全员信:列举8大问题 有同行比我们更出色
全球热议:比亚迪宋PLUS上月热销50006台:接棒哈弗H6成新一代神车
环球速看:从菜鸟到团队协同大神:产品经理工具技能修炼
当前聚焦:DTALK直播预约 | 金融行业嘉宾分享:金融机构数据治理实践路径
视焦点讯!ZooKeeper 避坑实践:SnapCount 设置不合理导致磁盘爆满,服务不可用
一纸死亡威胁:让安卓最良心的PS2模拟器凉凉了
世界讯息:年底发福利 马自达推出全系购车优惠:CX-5置换1万补贴
环球头条:AMD正式发布锐龙7000三款新U:一键能效暴涨47%!就看价格了
微动态丨增程混动加持 Aska A5飞行汽车首发亮相:配降落伞、可垂直起降
最新资讯:AMD锐龙7000降临笔记本:4种CPU/3种GPU/4种工艺 性能最高提升78%!
环球热头条丨索尼《GT赛车》真人电影!《头号赛车手》先导预告发布:8月上映
全球动态:确定了!漫威新片《黑豹2》2月1号正式上线流媒体
不减薪、工作5小时下班!实探“四天半工作制”乐视:比预想的还好
天天新资讯:《阿凡达1/2》仅是开胃菜?卡梅隆:好戏在后面
当前视讯!元旦就“入夏”?极端暖冬席卷欧洲:至少7国破气温记录
快看点丨修改NuGet包默认存放位置
环球快消息!AcWing1174. 受欢迎的牛
当前信息:苹果砍单立讯精密最受伤?官方回应:与客户合作正常
环球热讯:iPhone 15 Pro/Ultra升级!钛合金边框+8GB内存
天天视讯!内存暴跌4成 现在不买待何时?
iPhone 14 Pro全天候显示屏有多费电?实测每小时不到1%
环球今热点:今日发布 比亚迪仰望首款硬派越野车内饰谍照:百万级豪华
『JNPF』低代码创新赋能数字经济建设
【环球新视野】iPhone一直收集用户数据!隐私捍卫者苹果被法国重罚:我们不服
微信红包升级!全新动态红包封面上线
司机免费代驾870公里送卡友回家 获5千元正能量奖金:这魄力网友点赞
天天快看点丨《阿凡达2》 已经被“烂片之王”翻拍了:豆瓣居然全5星
神U换代 AMD Zen4架构锐龙7 7800X3D来了:游戏性能提升30%
微信支付--JSAPI支付(微信小程序和微信公众号支付都可以采用该方式)
13+3相豪华供电!影驰RTX 4070 Ti星曜OC显卡图赏
女子跨年夜中1000万后悔跟孩子说 他们说不奋斗了引网友热议:这能躺平?
环球热议:乘联会:预计2022年乘用车销量2070万辆 今年或0增长
存款贬值了快一半 土耳其人把游戏当成了救命稻草
每周只上班4天半!乐视居然成了"反卷斗士":真是神仙日子吗?
一本通动态规划篇解题报告
当前视讯!Python的保留字、标识符、变量的定义、常用数据类型、数据类型转换
砍单三大产品线 苹果市值跌破2万亿美元 富士康表态
世界热点评!抄底吗?知名投资人段永平:已将手上腾讯美股换成苹果
天天观速讯丨二次元外观下带来澎湃性能!铭瑄MS RTX 4070 Ti OC12G璦珈评测:最强192bit显卡非它莫属
10升好身材!ROG发布冰刃X迷你机:居然有没发布的RTX 4070
金庸最成功的作品 来源自历史上让人耻辱的失败
焦点要闻:500吨级!中国最强液体火箭发动机的“家”快建好了
世界信息:CF13C. Sequence
看点:设计模式简单介绍
胡伟武:Linux桌面软件生态是x86和ARM“软肋” 龙芯希望一两年后全面超过
丰田总裁再度质疑电动汽车:这会让车企降低价值!
每日资讯:RTX 4090加持:ROG发布新款XG Mobile显卡坞
即时:三星发布全球首款8K 150寸投影仪:离墙几毫米即可完成投射
焦点热文:画面太美!男子意外发现交通卡余额有172万 官方回应真相无奈
天天速看:写给大忙人看的Go语言快速指南(中文翻译)
天天实时:[概率论与数理统计]笔记:2.2 随机变量的数字特征
Python:numpy模块最详细的教程
python3实现字符串的全排列的方法(无重复字符)两种解决方法
全球快播:python中可以处理word文档的模块:docx模块
环球即时看!宏碁发布eKinekt BD 3酷骑桌:工作之余还能骑动感单车
世界热讯:1.6亿美元是罚定了!印度法庭驳回谷歌推翻垄断案的请求
当前热点-17万元起真香!奇瑞最高颜值SUV星途瑶光盲订量已达6012台
环球热点评!2022广州车展压轴登场 这八款新能源新车千万不要错过
今头条!全新NT架构加持!腾讯QQ原生上架麒麟应用商店
天天微资讯!国产可乐为什么都在陆续消失?专家道出原因
哄娃神器 一公司推出可自动驾驶婴儿车:售价约2.2万人民币
画风有《魔兽》那味了:国产多端MMO《塔瑞斯世界》PV首曝
【环球热闻】男子一口气网购20个26元扫地机器人:场面壮观实测失望
男子为研究显卡到网吧一口气拿7块:网友调侃要都是4090赚大
环球微资讯!Float value issue in GLSL
【环球热闻】事件总线 + 函数计算构建云上最佳事件驱动架构应用
实时:C罗说世界杯唯一赢阿根廷的是沙特 这里是新挑战 不是养老
配大哥H9同款2.0T 国产豪华轿跑红旗H6官图发布:罕见中置双排气
全球热头条丨微软再次挑战谷歌:Bing或将推出ChatGPT AI版本
【全球时快讯】一加首次推出100W双口充电器:支持65W PD快充 首发229元
世界观点:华系车崛起!欧洲每10台新能源汽车 就有1台来自中国
MySQL——索引
全球关注:易基因|METTL3 通过调节m6A 修饰抑制口腔鳞状细胞癌安罗替尼敏感性 | 肿瘤研究
环球今头条!苹果app怎么上架
天天看热讯:有史以来第一个6GHz CPU i9-13900KS现身中国!要卖6500元?
【当前热闻】3999元用4年依然流畅!一加11开启预售
热头条丨奥迪A6L提车三天出问题 4、5挡异响!4S店同意退车