你有一条区间\([0, X)\)，并且有一个数组\(L_1, ..., L_n\)。对于任意\(1 \leq i \leq n\)，你可以指定一个非负整数\(0 \leq j_i \leq X - L_i\)。求有多少种指定的方法，使得\([j_1, j_1 + L_1), [j_2, j_2 + L_2), ..., [j_n, j_n + L_n)\)能覆盖\([0, X)\)这段区间，输出这个方案数模\(1000000007\)的最小非负剩余。
约束条件
\(1 \leq N \leq 100\)
\(1 \leq L_i \leq X \leq 500\)
这是一个覆盖问题，考虑使用\(DP\)来解决。设\(f_i\)表示覆盖了\([0, i)\)的方案数。
发现无论怎么增加状态，这个\(DP\)无法正确的转移。
为什么？
不同长度的线段的先后覆盖无法由较少的状态来表示。
需要对这个问题进行转换。
使用容斥原理。
如果我们固定\(S \in [0, X) \bigcap Z\)，考虑求对于任意\(i \in S\)，\([i, i + 1)\)这段小区间不被任何\(n\)个区间覆盖的方案数。
那么考虑这\(\lvert S \rvert\) 段小区间把\([0, X)\)分为了\(k\)段，其中长度为\(i(1 \leq i \leq X)\)的段的个数是\(a_i\)。那么考虑这\(N\)段弧中的第\(i\)段弧可以放在哪里？
000111000011110001111110001
--- ---- --- ---
---111----1111---111111---1对\([j_i, j_i + L_i)\)，它必定在\(k\)段中的某一段，并且这一段的长度不小于\(L_i\)。若这一段长度是\(k\)，那么放法个数为\(k - L_i + 1\)。
因此，方案数为：
\[\prod_{i = 1}^{N} (\sum_{j \ge L_i} a_j (j + 1 - L_i)) \tag{1}\]
根据容斥原理，我们枚举\(S\)，计算方案数，再将它们乘以\((-1)^{\lvert S \rvert}\) 相加，就得到最终的答案。
复杂度为\(O(poly(N,X) \cdot 2^X)\)。
如何优化？
我们设有\(c_i(1 \leq i \leq X)\)个\(L\)数组的值为\(i\)。固定了\(a_1, ..., a_L\)后，对答案的贡献是：
\[ \prod_{i = 1}^{X} \frac{1}{a_i!} (\sum_{j \ge i} a_j (j + 1 - i))^{c_i} \tag{2} \\ \cdot (\sum_{i = 1}^{X} a_i)! \\\cdot (-1)^{X - \sum_{i = 1}^{X} ia_i} \\ \cdot {{X - \sum_{i = 1}^{X} ia_i + 1} \choose {\sum_{i = 1}^{X} a_i}}\]
（<1> 固定了\(a_1, ..., a_L\)，\(N\)个区间有多少种放法 <2> 考虑如果将这些空的段按照某个顺序排起来 <3> 如何从这些空的段的相对位置还原出\(S\)）
是不是很容易想到倒着\(DP\)计算这个式子呢？
我们按\(i\)从大到小\(DP\)，在\(DP\)的时候，我们固定的是\(a_i, a_{i + 1}, ..., a_X\)的取值，\(DP\)的状态需要记录:
(1) $ j = \sum_{m = i}^{X} a_m$
(2) \(k = \sum_{m = i}^{X} ma_m\)
设\(f_{i, j, k}\)表示固定了\(a_i, a_{i + 1}, ..., a_{X}\)的取值，以及当\(j = \sum_{m = i}^{X} a_m\)，\(k = \sum_{m = i}^{X} ma_m\)时\((2)\)式\(\ge i\)的部分的乘积之和。
（就是\(\prod_{m = i}^{X} \frac{1}{a_m!} (\sum_{j \ge m} a_j (j + 1 - m))^{c_m}\)的和）
容易写出转移式：
\[f_{i, j, k} = \sum_{l = 0}^{j} f_{i + 1, j - l, k - i\cdot l} \cdot \frac{1}{l!} \cdot (k - (i - 1) \cdot j)^{c_i} \tag {3}\]
最终答案为:
\[ \sum_{i = 0}^{X} \sum_{j = 0}^{\min (i + 1, x)} (-1)^{X - j} {{X - j + 1} \choose i} i! f_{1, i, j}\]
直接计算似乎会超时，如何通过此题？
状态中\((i, j, k)\)满足\(k \ge i \cdot j \rightarrow j \leq [\frac{X}{i}]\)。
要计算复杂度，就是要计算四元有序非负整数数组\((i, j, k, l)\)中满足\(1 \leq i \leq X, 0 \leq j, k, l \leq X, k \ge i \cdot j,l \leq j\)的量级。
先固定\(i\)，则\(0 \leq l \leq j \leq [\frac{X}{i}]\),\((l, j)\)的取值有\(O(\frac{X^2}{i^2})\) 种。
而总共有\(\sum_{i = 1}^{X} \frac{X^2}{i^2} < \frac{\pi ^2}{6} X^2\) （\(\sum_{i = 1}^{\infin} {\frac{1}{i^2} < 1 + \sum_{i = 2}^{\infin} \frac{1}{i(i - 1)}} = 1 + \sum_{i = 2}^{+\infin} \frac{1}{i - 1} - \frac{1}{i} = 2\)。）
且\(k\)的取值一共有\(O(X)\)种，故实际上这样的四元有序数组个数是\(O(X^3)\)的。
时间复杂度\(O(X^3)\)，可以通过此题。
Dwango Programming Contest 6th E 题解
原文：https://www.cnblogs.com/mathematician/p/12521912.html