So easy?...
第一种：直接得到 $(n+1)^2$。
第二种：将 $(k+1)^2$ 拆成 $k^2 + 2k + 1$， 我知道 $\sum\limits_{k=0}^{n}k = \frac{n(n+1)}{2}$ ， 那么我可以算出 $$ G(n) = F(n) + n\cdot (n+1) + (n+1) $$
两种算法结果是一致的，这似乎并没有给出任何信息？ 😅
实际上只是你知道得太多了。 如果一个外星人👽没有听过神童高斯的故事，它可能就通过这种方式来推导 $\sum\limits_{k=0}^{n}k$。 聪明的外星人🤓还会用这种方法计算 $\sum\limits_{k=0}^{n}k^2,\sum\limits_{k=0}^{n}k^3,\cdots$
对于多项式 $f(n)$，它有这样形式的前缀和函数 $$ g(n) = \sum\limits_{k=0}^{n} f(i) $$ 上面讨论的是 $f(n) = n^{d}$ 的特例。可以知道，$g(n)$ 是一个 $d+1$ 次多项式。
多项式前缀和的结果是一个次数高一次的多项式。
这个技巧出现在 NOIP2020 微信步数，以及众多模拟题中。
它有一个比较固定的搭配技巧，即维护一些多项式的点值（而非系数）进行转移。然后再通过点值还原多项式的系数（Lagrange 插值），此处暂且不表，仅作初步印象。
如何快速枚举 n 的因子？ （算法层面的分类）
如何简单估计 n 的因子数量？ （理论层面的分类）
根号分治，就是将讨论的对象，按照一个阈值划分成两类。 通过一点分析，发现阈值接近根号时最优。
观察：$ \left\lfloor \frac{n}{i} \right\rfloor $ 是一个单调递减的函数
对于不同的值 $v$，能快速找到所有 $i$ 满足 $ \lfloor \frac{n}{i} \rfloor = v $
区间 $[l, r]$ 使得 $\lfloor \frac{n}{i} \rfloor$ 值相同，批量处理
初始化： $ i = 1 $
计算当前值： $ v = \left\lfloor \frac{n}{i} \right\rfloor $
确定区间右端点： $ r = \left\lfloor \frac{n}{v} \right\rfloor $
累计贡献： $ v \times (r - i + 1) $
更新 $ i = r + 1 $，重复直到 $ i > n $
考虑函数 $$ f(i) = \left\lfloor \frac{n}{i} \right\rfloor $$
对于固定商值 $v$，满足：
$$ \left\lfloor \frac{n}{i} \right\rfloor = v \iff v \le \frac{n}{i} < v+1 $$
对 $i$ 解不等式：
$$ \frac{n}{v+1} < i \le \frac{n}{v} $$
区间内的所有 $i$ 具有相同的函数值 $v$，可批量处理
使用 根号分治 分析复杂度。
提示：我们只需要考虑区间的数量。区间可以根据右端点的特征，分为两类。一类 $\le \sqrt{n}$，另一类 $> \sqrt{n}$。
对于二重求和
$$ \sum_{i=1}^n \sum_{j=1}^m a_{i,j} $$交换求和顺序
$$ \sum_{i=1}^n \sum_{j=1}^m a_{i,j} = \sum_{j=1}^m \sum_{i=1}^n a_{i,j} $$计算 $$ S = \sum_{i=1}^n \sum_{j=1}^{i} f(i,j) $$
交换求和顺序，改写为 $$ S = \sum_{j=1}^n \sum_{i=j}^{n} f(i,j) $$
换序其实是改变对同一集合 $R$ 的遍历顺序，求和结果不变。
比如：
$$ \sum_{i=1}^n \sum_{j=1}^i a_{i,j} = \sum_{j=1}^n \sum_{i=j}^n a_{i,j} $$两边都是对同一区域
$$ R = \{(i,j) \mid 1 \leq j \leq i \leq n \} $$把 $(i,j)$ 看成二维平面上的点
求和区域 $R$ 是二维点集，比如一个“下三角形”
换序就是改变遍历顺序：
多重求和不限于二维，三维、四维都可以类似用区域描述：
$$ \sum_{(i,j,k) \in R} a_{i,j,k} $$换序即调整变量遍历顺序，但区域不变。
很多地方把莫比乌斯反演定义成：
设两个函数 $f(n), g(n)$ 满足
$$ f(n) = \sum_{d \mid n} g(d) $$
则可以得到
$$ g(n) = \sum_{d \mid n} \mu\left(\frac{n}{d}\right) f(d) $$
这个语境下，反演可以解释成：
正向地，可以通过 $g$ 的（整除）前缀和表示出 $f$；
反向地，如何用 $f$ 的（整除）前缀和表示出 $g$。
莫比乌斯反演公式只是反演公式的一角。除了莫比乌斯反演，其实还有二项式反演，最值反演，等。
可以说它们都是容斥原理。通过一组容斥系数，使得最后只有我们想要的东西产生非零的贡献。
对任意逻辑命题 \(P\)，定义 Iverson 括号：
$$ [P] = \begin{cases} 1, & \text{如果 } P \text{ 为真} \\ 0, & \text{如果 } P \text{ 为假} \end{cases} $$也称作指示函数（indicator function）。
判断 \(x\) 是否为偶数：
$$ [x \equiv 0 \pmod 2] = \begin{cases} 1, & \text{若 } x \text{ 是偶数} \\ 0, & \text{否则} \end{cases} $$利用 Iverson 括号简化求和条件：
$$ \sum_{k} [k \text{ 满足某条件}] \cdot f(k) $$跳过不满足条件的项。
一般我们希望简化求和，把一个求和表示成一个简单函数。
一种迂回的战术：一个简单函数拆成求和，然后作和式变换，重新变回一个更好计算的简单形式。
在纯粹的数论和式变换题，我们经常会直接使用对应的容斥系数公式，来拆开一个简单函数。
而在一些综合题里面，我们更倾向于去发现，是不是有两类 dp 数组符合（数论）前缀和的关系。
反演公式使得我们只需要找出一个方向的表示，就可以知道另一个方向😋。
如果把二项式系数拆开，二项式反演即 $$ \frac{f_n}{n!} = \sum_k \left(\frac{g_k}{k!}\right) \cdot \left(\frac{1}{(n-k)!}\right) $$ 右边其实是多项式卷积的形式。从序列的角度 $$ \left\{\frac{f_n}{n!}\right\} = \left\{\frac{g_n}{n!}\right\} * \left\{\frac{1}{n!}\right\} $$
把上面三个序列分别放进形式幂级数 $F(x),G(x),H(x)$。
实际上 $H(x)$ 就是经典的 $e^x$。于是 $$ F(x) = G(x) \times e^{x} \Leftrightarrow G(x) = F(x) \times e^{-x} $$ 可以验证 $e^{-x}$ 对应的序列，正是 $\left\{\frac{(-1)^n}{n!}\right\}$。
除了理论层面给出另一种理解，算法层面，也允许我们使用 FFT 将 $g_i,i=0,1,\cdots,n$ 的信息， 用 $O(n\log n)$ 的时间转换成 $f_{i},i=0,1,\cdots,n$ 的信息。反之亦然。