不定方程的解的個(gè)數(shù)

Lv0

? 首先我們看這樣一個(gè)問(wèn)題，求 $\sum _{i=1}^n{x}_i=b$ 的非負(fù)整數(shù)解的個(gè)數(shù)。

? 這個(gè)問(wèn)題就非常簡(jiǎn)單啊，我們稍微把他轉(zhuǎn)化一下，這個(gè)問(wèn)題就等價(jià)于有 $n$ 個(gè)小朋友分 $b$ 個(gè)糖果，每個(gè)小朋友至少分到 $0$ 個(gè)糖果（好慘啊），求分完糖果的方案數(shù)。

? 然后我們?cè)俎D(zhuǎn)化一下問(wèn)題，現(xiàn)在有 $b$ 個(gè)糖果排成一排，在其中放 $n?1$ 個(gè)木板（可以有多個(gè)木板在同一個(gè)格子里），這樣就能把這些糖果分成 $n$ 部分，求方木板的方案數(shù)。

? 這樣就很顯然了嘛，答案就是總共有 $n+b?1$ 個(gè)格子可選，在其中選出 $n?1$ 個(gè)格子的方案數(shù)，也就是 $C_{n+b?1}^{n?1}$。

Lv1

? 還有這樣一個(gè)問(wèn)題，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\ge l_i$ 的非負(fù)整數(shù)解數(shù)。顯然我們非常不希望出現(xiàn)后面的約束條件，于是我們考慮這樣：

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

? 這樣一來(lái)我們就把問(wèn)題轉(zhuǎn)化成了第一個(gè)問(wèn)題一樣的形式了（就相當(dāng)于我們減掉了 $x_i<l_i$ 的貢獻(xiàn)），答案就是：

$$ans=?\begin{array}{c}n+b?\sum _{i=1}^n{l}_i?1\\ n?1\end{array}?$$

Lv2

? 最后一個(gè)問(wèn)題，求 $\sum _{i=1}^n{x}_i=b$ 且 $x_i\le r_i$ 的非負(fù)整數(shù)解的個(gè)數(shù)。這個(gè)問(wèn)題就不像上一個(gè)那么好轉(zhuǎn)換了。所以我么考慮容斥掉 $x_i\ge r_i+1$ 的貢獻(xiàn)。

? 我們令集合 $S$ 表示 $\sum _{i=1}^n(x_i\ge r_i+1)$ 的二進(jìn)制集合。這樣就相當(dāng)于求 S = { 0 , 0 , ? ? , 0 } S = \{ 0, 0, \cdots, 0 \} S={0,0,?,0} 的時(shí)候的答案。我們令 $f(S)$ 表示該二進(jìn)制集合為 $S$ 時(shí)的答案。則有：

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$ 表示總數(shù)，也就是第一個(gè)問(wèn)題的答案。 U = { 0 , 0 , ? ? , 0 } U = \{ 0, 0, \cdots, 0 \} U={0,0,?,0} （$n$ 個(gè) $0$）。上面這個(gè)式子就是容斥原理嘛。

? 然后其中（等價(jià)于第二個(gè)問(wèn)題）：

$$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}$$