前言：

作为一名OIer，数学推导一定不能差。

例子：

用尽量快的方法求以下式子：

1. ${\sum }_{i=0}^{n-1}{a}^i\ast b^{n-1-i}(n\in N_{+})$
2. ${\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i(2|n)$
3. ${\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i(n=2k+1,k\in N_{+})$
4. ${\sum }_{i=1}^n{i}^2$

用$\sum$只是为了好看，建议读者把求和式展开。

公式：

1. $a^n-b^n=(a-b)\ast {\sum }_{i=0}^{n-1}{a}^i\ast b^{n-1-i}(n\in N_{+})$
2. $a^n-b^n=(a+b)\ast {\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i(2|n)$
3. $a^n+b^n=(a+b)\ast {\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i(n=2k+1,k\in N_{+})$
4. ${\sum }_{i=1}^n{i}^2=n\ast (n+1)\ast (2n+1)/6$

推导：

1. $a^n-b^n=(a-b)\ast {\sum }_{i=0}^{n-1}{a}^i\ast b^{n-1-i}(n\in N_{+})$

$$右边=\sum _{i=1}^n{a}^i\ast b^{n-i}-\sum _{i=0}^{n-1}{a}^i\ast b^{n-i}$$
$$=a^n\ast b^0-a^0\ast b^n=a^n-b^n$$

2. $a^n-b^n=(a+b)\ast {\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i(2|n)$

$$右边=\sum _{i=0}^{n-1}(-1{)}^i\ast a^{n-i}\ast b^i-\sum _{i=1}^n(-1{)}^{i-1}\ast a^{n-i}\ast b^i=a^n-b^n$$

3. 类似2的证明。

4.${\sum }_{i=1}^n{i}^2=n\ast (n+1)\ast (2n+1)/6$

$$n^3-(n-1{)}^3=1\ast [n^2+(n-1{)}^2+n(n-1)]$$
$$=n^2+(n-1{)}^2+n^2-n$$
$$=2\ast n^2+(n-1{)}^2-n$$
$$n^3-1^3=n^3-(n-1{)}^3+(n-1{)}^3-(n-2{)}^3\dots \dots +2^3-1^3$$
$$n^3-1^3=2\ast (2^2+3^2+...+n^2)+[1^2+2^2+...+(n-1{)}^2]-(2+3+4+...+n)$$
$$n^3-1=2\ast (1^2+2^2+3^2+...+n^2)-2+[1^2+2^2+...+(n-1{)}^2+n^2]-n^2-(2+3+4+...+n)$$
$$n^3-1=3\ast (1^2+2^2+3^2+...+n^2)-2-n^2-(1+2+3+...+n)+1$$
$$n^3-1=3(1^2+2^2+...+n^2)-1-n^2-n(n+1)/2$$
$$3(1^2+2^2+...+n^2)=n^3+n^2+n(n+1)/2=(n/2)(2n^2+2n+n+1)=(n/2)(n+1)(2n+1)$$
$$1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6$$

结论：

1. ${\sum }_{i=0}^{n-1}{a}^i\ast b^{n-1-i}=(a^n-b^n)/(a-b)(n\in N_{+})$
2. ${\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i=(a^n-b^n)/(a+b)(2|n)$
3. ${\sum }_{i=0}^{n-1}(-1{)}^i\ast a^{n-1-i}\ast b^i=(a^n+b^n）/(a+b)(n=2k+1,k\in N_{+})$
4. ${\sum }_{i=1}^n{i}^2=n\ast (n+1)\ast (2n+1)/6$

1~3$都由可以用快速幂从O(n)优化到O(logn).$

4由$O(n)优化成O(1)$.

推广：

如果1~3要求取模，那就用快速幂+乘法逆元。