不定方程的解的个数
Lv0
首先我们看这样一个问题，求 ），求分完糖果的方案数。
然后我们再转化一下问题，现在有 b b b 个糖果排成一排，在其中放 n − 1 n - 1 n−1 个木板（可以有多个木板在同一个格子里），这样就能把这些糖果分成 n n n 部分，求方木板的方案数。
这样就很显然了嘛，答案就是总共有 n + b − 1 n + b - 1 n+b−1 个格子可选，在其中选出 n − 1 n - 1 n−1 个格子的方案数，也就是 C n + b − 1 n − 1 C_{n + b - 1}^{n - 1} Cn+b−1n−1。
Lv1
还有这样一个问题，求 ∑ i = 1 n x i = b \sum\limits_{i = 1}^nx_i = b i=1∑nxi=b 且 x i ≥ l i x_i \geq l_i xi≥li 的非负整数解数。显然我们非常不希望出现后面的约束条件，于是我们考虑这样：
∑ i = 1 n x i = b − ∑ i = 1 n l i \sum_{i = 1}^nx_i = b - \sum_{i = 1}^nl_i i=1∑nxi=b−i=1∑nli
这样一来我们就把问题转化成了第一个问题一样的形式了（就相当于我们减掉了 x i < l i x_i < l_i xi<li 的贡献），答案就是：
a n s = ( n + b − ∑ i = 1 n l i − 1 n − 1 ) ans = \begin{pmatrix} n + b - \sum\limits_{i = 1}^n l_i - 1 \\ n - 1 \end{pmatrix} ans=⎝ ⎛n+b−i=1∑nli−1n−1⎠ ⎞
Lv2
最后一个问题，求 ∑ i = 1 n x i = b \sum\limits_{i = 1}^nx_i = b i=1∑nxi=b 且 x i ≤ r i x_i \leq r_i xi≤ri 的非负整数解的个数。这个问题就不像上一个那么好转换了。所以我么考虑容斥掉 x i ≥ r i + 1 x_i \geq r_i + 1 xi≥ri+1 的贡献。
我们令集合 S S S 表示 ∑ i = 1 n ( x i ≥ r i + 1 ) \sum\limits_{i = 1}^n(x_i \geq r_i + 1) i=1∑n(xi≥ri+1) 的二进制集合。这样就相当于求 S = { 0 , 0 , ⋯ , 0 } S = \{ 0, 0, \cdots, 0 \} S={0,0,⋯,0} 的时候的答案。我们令 f ( S ) f(S) f(S) 表示该二进制集合为 S S S 时的答案。则有：
f ( S = { 0 , 0 , ⋯ , 0 } ) = t o t − ∑ S ⊂ U ( − 1 ) ∣ S ∣ + 1 f ( S ) f(S = \{0, 0, \cdots, 0\}) = tot - \sum_{S \subset U}(-1)^{|S| + 1}f(S) f(S={0,0,⋯,0})=tot−S⊂U∑(−1)∣S∣+1f(S)
其中 t o t tot tot 表示总数，也就是第一个问题的答案。 U = { 0 , 0 , ⋯ , 0 } U = \{ 0, 0, \cdots, 0 \} U={0,0,⋯,0} （ n n n 个 0 0 0）。上面这个式子就是容斥原理嘛。
然后其中（等价于第二个问题）：
f ( S ) = ( n + b − 1 − ∑ i ∈ S ( r i + 1 ) n − 1 ) f(S) = \begin{pmatrix} n + b - 1 - \sum\limits_{i \in S} (r_i + 1) \\ n - 1 \end{pmatrix} f(S)=(n+b−1−i∈S∑(ri+1)n−1)
于是：
a n s = ( n + b − 1 n − 1 ) − ∑ S ⊂ U ( − 1 ) ∣ S ∣ + 1 f ( S ) = ( n + b − 1 n − 1 ) + ∑ S ⊂ U ( − 1 ) ∣ S ∣ ( n + b − 1 − ∑ i ∈ S ( r i + 1 ) n − 1 ) = ∑ S ⊆ U ( − 1 ) ∣ S ∣ f ( S ) \begin{aligned} ans & = \begin{pmatrix} n + b - 1 \\ n - 1 \end{pmatrix} - \sum_{S \subset U}(-1)^{|S| + 1} f(S) \\ & = \begin{pmatrix} n + b - 1 \\ n - 1 \end{pmatrix} + \sum_{S \subset U} (-1)^{|S|} \begin{pmatrix} n + b - 1 - \sum\limits_{i \in S}(r_i + 1) \\ n - 1 \end{pmatrix} \\ & = \sum_{S \subseteq U} (-1)^{|S|}f(S) \end{aligned} ans=(n+b−1n−1)−S⊂U∑(−1)∣S∣+1f(S)=(n+b−1n−1)+S⊂U∑(−1)∣S∣(n+b−1−i∈S∑(ri+1)n−1)=S⊆U∑(−1)∣S∣f(S)