问题

这是一道模拟赛趣题。

给出方程:

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

其中 fixigi(1in)f_i \le x_i \le g_i(1 \le i \le n)

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

数据范围:

n20,1gifi1012n\le20,1\le g_i \le f_i\le10^{12}

解法

Lamma1

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

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

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

答案为 Cns+1sC_{n-s+1}^s

证明:

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

也就是 ss 个相同的求放进 nn 个不同的盒子,且每个盒子至少 11 个球(隔板问题)。

即从 ss 个球中间的 s1s-1 个位置选择 n1n-1 个放置隔板,答案为 Cs1n1C_{s-1}^{n-1}

这个对应了方程

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

的合法解数。

那设 xi=xi+1x_i'=x_i + 1,上面柿子等价于:

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

的正整数解的个数为 Cn+s1n1=Cn+s1sC_{n+s-1}^{n-1}=C_{n+s-1}^{s}

证毕。

Lamma1 的推论(不定元有下界的整数解个数)

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

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

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

yi=xipiy_i = x_i - p_i。上述方程等价为:

i=1nyi=si=1npi\sum_{i=1}^ny_i=s - \sum_{i=1}^np_i

由 Lamma1 可得答案为:

Cn+si=1npi1si=1npiC_{n+ s - \sum_{i=1}^np_i-1}^{s - \sum_{i=1}^np_i}

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

yi=xifiy_i = x_i - f_i

0yigifi0 \le y_i \le g_i - f_i

则原题目化为:

i=1nyi=si=1nfi\sum\limits_{i=1}^n y_i = s - \sum\limits_{i=1}^n f_i

的个数。设他的解集为 SSs=si=1nfis'=s - \sum\limits_{i=1}^n f_i则有:

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

PiP_i 为性质 yigifi+1y_i \ge g_i - f_i + 1AiA_i 表示满足性质 PiP_i 的解构成的集合。

根据容斥原理有:

Ans=i=1nAi=S1inAi+1i<j<nAiAj11<j<knAiAjAk++(1)nA1A2AnAns =\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 的推论求就可以了。