对于 Newton Expansion，式子本身的证明其实无甚可翻新的花样，但是题还是很有意思的。比如 codeforces - 1332E Height All the Same 这个。
首先给出几个性质：每个 cell 上的数字奇偶性才是需要关注的；如果 $n\times m$ 为奇数，永远有解；如果 $n\times m$ 为偶数，当 $\sum\sum a_{i,j}\bmod2$ 为偶数时有解。应该都不需要证明。
奇数的答案不赘，我们可以写出偶数的答案式子：$\displaystyle\sum_{i=0}^{\lfloor\frac{nm}{2}\rfloor}a^{2i}b^{nm-2i}\binom{nm}{2i}$，$a,b$ 分别是 $[l,r]$ 中偶 / 奇的数量。然后你注意这个式子长得很像 Newton Expansion 的形式，容易构造出答案为 $\frac{(a+b)^{nm}+(a+b)^{nm}}{2}$。
我们来看几个一般的组合恒等式。
- $\displaystyle\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$；
- $\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$；
- $\displaystyle\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$；
- $\displaystyle\sum_{k=0}^{n}k^2\binom{n}{k}=n(n+1)2^{n-2}$；
- $\displaystyle\sum_{l=0}^n\binom{l}{k}=\binom{n+1}{k+1}\Longrightarrow\sum_{k=0}^n\binom{r+k}{k}=\binom{r+n+1}{r+1}=\binom{r+n+1}{n}$；
- $\displaystyle\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$；
- $\displaystyle\sum_{k=0}^m(-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}$；
- $\displaystyle\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}$；
- $\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$；（Vandermonde Convolution）
我们一个一个的来看。
- 这个我无法找到除了代数解释以外的方法来诠释它的含义；
- 经典的 Pascal's Formula，组合意义即钦定一个物品不选。适用场景很多，经常反过来用；
- 带权变下项求和，考虑这样的组合意义：在 $n$ 个物品中选出 $k$ 个，再从这 $k$ 个物品中选出一个组成 1-tuples 的方案数。对应到 r.h.s.，反过来钦定 1-tuples，然后计算系数。
- 同理，组合意义即在 $n$ 个物品中选出 $k$ 个，再从这 $k$ 个物品中可重地选出两个物品组成无序 2-tuples 的方案数。对应到 r.h.s.，反过来钦定 2-tuples，再考虑系数。需要分类讨论，当选出的物品不相同，为 $n(n-1)2^{n-2}$，当相同时，为 $n^22^{n-1}$，加在一起即 $n(3n-1)2^{n-2}$。
- 变上项求和，考虑 $n+1$ 个物品，每次钦定第 $1,2,\dots,n+1$ 个不选，左右两式即相等，例题 codechef - CSEQ Count Sequences。
- 这个式子我理解不能，但是运算有封闭性，再算一次可以变回去。
- 用式 6，得 $\displaystyle \sum_{k=0}^m(-1)^k\binom{n}{k}=\sum_{k=0}^m\binom{k-n-1}{k}=\sum_{k=0}^m\binom{k-n-1}{}$ 🕊。
- 组合意义：$\{a_{n}\}$ 的 $r$-subsets 的 $k$-subsets 数，r.h.s. 即在 $\{a_n\}$ 中选出 $k$-subsets，再在 ${a_n}\setminus k\text{-subsets}$ 中选 $r-k$-subsets。
- l.h.s. 和 r.h.s. 的意义都是 $\{a_{m+n}\}$ 的 $r$-subsets 数。
来看一些题。
- 「acmhdu - 5794」A Simple Chess link：首先注意到这个走路的方式就是象棋马走日，然后做一个像 codeforces - 559C Gerald and Giant Chess 一样的 dp，有些细节需要注意。
- 「codeforces - 839D」Winter is here link：数数日门题。考虑反过来算每种 $\gcd$ 的贡献次数。