不定方程的解的个数

Lv0

  首先我们看这样一个问题，求 $\sum _{i=1}^n{x}_i=b$ 的非负整数解的个数。

  这个问题就非常简单啊，我们稍微把他转化一下，这个问题就等价于有 $n$ 个小朋友分 $b$ 个糖果，每个小朋友至少分到 $0$ 个糖果（好惨啊），求分完糖果的方案数。

  然后我们再转化一下问题，现在有 $b$ 个糖果排成一排，在其中放 $n-1$ 个木板（可以有多个木板在同一个格子里），这样就能把这些糖果分成 $n$ 部分，求方木板的方案数。

  这样就很显然了嘛，答案就是总共有 $n+b-1$ 个格子可选，在其中选出 $n-1$ 个格子的方案数，也就是 $C_{n+b-1}^{n-1}$。

Lv1

  还有这样一个问题，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\ge l_i$ 的非负整数解数。显然我们非常不希望出现后面的约束条件，于是我们考虑这样：

$$\sum _{i=1}^n{x}_i=b-\sum _{i=1}^n{l}_i$$

  这样一来我们就把问题转化成了第一个问题一样的形式了（就相当于我们减掉了 $x_i<l_i$ 的贡献），答案就是：

$$ans=\left(\begin{array}{c}n+b-\sum _{i=1}^n{l}_i-1\\ n-1\end{array}\right)$$

Lv2

  最后一个问题，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\le r_i$ 的非负整数解的个数。这个问题就不像上一个那么好转换了。所以我么考虑容斥掉 $x_i\ge r_i+1$ 的贡献。

  我们令集合 $S$ 表示 $\sum _{i=1}^n(x_i\ge r_i+1)$ 的二进制集合。这样就相当于求 S = { 0 , 0 , ⋯   , 0 } S = \{ 0, 0, \cdots, 0 \} S={0,0,⋯,0} 的时候的答案。我们令 $f(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)

  其中 $tot$ 表示总数，也就是第一个问题的答案。 U = { 0 , 0 , ⋯   , 0 } U = \{ 0, 0, \cdots, 0 \} U={0,0,⋯,0} （$n$ 个 $0$）。上面这个式子就是容斥原理嘛。

  然后其中（等价于第二个问题）：

$$f(S)=\left(\begin{array}{c}n+b-1-\sum _{i\in S}(r_i+1)\\ n-1\end{array}\right)$$

  于是：

$$\begin{array}{rl}ans& =\left(\begin{array}{c}n+b-1\\ n-1\end{array}\right)-\sum _{S\subset U}(-1{)}^{|S|+1}f(S)\\ & =\left(\begin{array}{c}n+b-1\\ n-1\end{array}\right)+\sum _{S\subset U}(-1{)}^{|S|}\left(\begin{array}{c}n+b-1-\sum _{i\in S}(r_i+1)\\ n-1\end{array}\right)\\ & =\sum _{S\subseteq U}(-1{)}^{|S|}f(S)\end{array}$$