不定元任意范围的整数解个数

问题

这是一道模拟赛趣题。

给出方程：

$$\sum_{i=1}^nx_i=s$$

其中 $f_i \le x_i \le g_i(1 \le i \le n)$。

求这个方程组的解的个数 $ans \% 1000000007$。

数据范围：

$n\le20,1\le g_i \le f_i\le10^{12}$。

解法

Lamma1

$$\sum_{i=1}^nx_i=s$$

其中 $\forall x_i \in \mathbb{N}(1 \le i \le n)$。

求这个方程组的解的个数。

答案为 $C_{n-s+1}^s$。

证明：

先考虑 $\forall x_i\neq 0$ 的情况。

也就是 $s$ 个相同的求放进 $n$ 个不同的盒子，且每个盒子至少 $1$ 个球(隔板问题)。

即从 $s$ 个球中间的 $s-1$ 个位置选择 $n-1$ 个放置隔板，答案为 $C_{s-1}^{n-1}$。

这个对应了方程

$$\sum_{i=1}^nx_i=s(x_i \in \mathbb{Z}^+)$$

的合法解数。

那设 $x_i'=x_i + 1$，上面柿子等价于：

$$\sum_{i=1}^nx_i'=s+n$$

的正整数解的个数为 $C_{n+s-1}^{n-1}=C_{n+s-1}^{s}$。

证毕。

Lamma1 的推论（不定元有下界的整数解个数）

$$\sum_{i=1}^nx_i=s$$

其中 $\forall x_i \in \mathbb{Z}(1 \le i \le n),x_i \ge p_i$。

求这个方程组的解的个数。

另 $y_i = x_i - p_i$。上述方程等价为：

$$\sum_{i=1}^ny_i=s - \sum_{i=1}^np_i$$

由 Lamma1 可得答案为：

$$C_{n+ s - \sum_{i=1}^np_i-1}^{s - \sum_{i=1}^np_i}$$

不定元任意范围的整数解个数

设 $y_i = x_i - f_i$。

则 $0 \le y_i \le g_i - f_i$。

则原题目化为:

$$\sum\limits_{i=1}^n y_i = s - \sum\limits_{i=1}^n f_i$$

的个数。设他的解集为 $S$，$s'=s - \sum\limits_{i=1}^n f_i$则有：

$$|S| = C_{n+s'-1}^{s'}$$

设 $P_i$ 为性质 $y_i \ge g_i - f_i + 1$，$A_i$ 表示满足性质 $P_i$ 的解构成的集合。

根据容斥原理有：

$$Ans =\bigcap_{i=1}^n |\overline{A_i}| = |S| - \sum_{1 \le i \le n}|A_i| + \sum_{1 \le i < j < n}|A_i \cap A_j| - \sum_{1 \le 1 < j < k \le n}|A_i \cap A_j \cap A_k| + \cdots + (-1)^n|A_1 \cap A_2 \cap \cdots \cap A_n|$$

然后每一项分开来使用组合数学和 Lamma1 的推论求就可以了。