题目大意
你有一条区间([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) igcap Z)，考虑求对于任意(i in S)，([i, i + 1))这段小区间不被任何(n)个区间覆盖的方案数。
那么考虑这(lvert S vert) 段小区间把([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)。
因此，方案数为：
根据容斥原理，我们枚举(S)，计算方案数，再将它们乘以((-1)^{lvert S vert}) 相加，就得到最终的答案。
复杂度为(O(poly(N,X) cdot 2^X))。
如何优化？
第二个想法
我们设有(c_i(1 leq i leq X))个(L)数组的值为(i)。固定了(a_1, ..., a_L)后，对答案的贡献是：
（<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})的和）
容易写出转移式：
最终答案为:
直接计算似乎会超时，如何通过此题？
复杂度分析
状态中((i, j, k))满足(k ge i cdot j ightarrow 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))，可以通过此题。
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << (x) << endl
using namespace std;
const int N = 105, X = 505;
const long long mod = 1000000007ll;
int n, x, cnt[X];
long long c[X][X], f[X][X], g[X][X];
long long qpow (long long a, long long b) {
long long res = 1ll;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
int main () {
cin >> n >> x;
for (int i = 1; i <= x; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) {
int l;
cin >> l;
cnt[l]++;
}
for (int i = 0; i <= x; i++) c[i][0] = c[i][i] = 1ll;
for (int i = 1; i <= x; i++) {
for (int j = 1; j < x; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= x; j++) f[i][j] = 0ll;
}
f[0][0] = 1ll;
for (int i = x; i >= 1; i--) {
for (int j = 0; j <= x; j++) {
for (int k = i * j; k <= x; k++) {
long long coef = qpow(k - (i - 1) * j, cnt[i]);
g[j][k] = 0ll;
for (int l = 0; l <= min(j, k / i); l++) g[j][k] = (g[j][k] + f[j - l][k - l * i] * c[j][l] % mod * coef) % mod;
}
}
for (int j = 0; j <= x; j++) {
for (int k = 0; k <= x; k++) f[j][k] = g[j][k];
}
}
long long ans = 0ll;
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= min(x, i + 1); j++) {
if (i & 1) ans = (ans + mod - f[j][x - i] * c[i + 1][j]) % mod;
else ans = (ans + f[j][x - i] * c[i + 1][j]) % mod;
}
}
printf("%lld
", ans);
return 0;
}