不定方程的解的個數

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=?\begin{array}{c}n+b?\sum _{i=1}^n{l}_i?1\\ n?1\end{array}?$$

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?U}(?1{)}^{|S|+1}f(S)\\ & =\left(\begin{array}{c}n+b?1\\ n?1\end{array}\right)+\sum _{S?U}(?1{)}^{|S|}\left(\begin{array}{c}n+b?1?\sum _{i\in S}(r_i+1)\\ n?1\end{array}\right)\\ & =\sum _{S?U}(?1{)}^{|S|}f(S)\end{array}$$