Problem – A – Codeforces

题意：给定一个长为 $n$ 的序列 $a_i$, 要求构造非严格递减序列 $b_i$, 满足 $a_i \le b_i \le R$, 求方案数. $n \le 5 \times 10 ^ 3, R, a_i \le 10 ^ 9$.

做法： $a_i$ 的范围太大了, 不能简单地记录上一位的值.
考虑使用容斥. 方便起见把 $a_i$ 直接变成 $R – a_i + 1$, 条件就变成了 $b_i \le a_i$ 且 $b_i \ge b_{i – 1}$.
这里有两个限制条件, 可以固定 $b_i \le a_i$ 是必须满足的条件, 只对 $b_i \ge b_{i – 1}$ 使用容斥, 枚举哪些位置是比上一位小的(违反限制), 其他位置随意.
枚举后的形态一定是有若干个区间是严格递减的, 其他位置随意. 考虑如果一个区间 $[l, r]$ 是严格递减的, 显然所有的数都 $< a_l$, 所以这段区间的方案数就是 ${a_l \choose r – l + 1}$. 另外实际上 $b_l$ 是没有违反限制的, 所以这里对系数的贡献是 $(-1) ^ {r – l}$.
考虑令 $dp_i$ 表示只考虑前 $i$ 个位置的答案, 转移时自然就是枚举一个 $j$, 然后计算 $dp_{j – 1}$ 乘上区间 $[j, i]$ 严格递减的方案数. 另外还有一种情况是 $b_i$ 没有违反限制, 这时显然直接在 $dp_{i – 1}$ 的基础上乘上一个 $a_i$ 就好了.

(转移时还要注意, 由于枚举的是严格递减区间, 自然就不能枚举只有一个数的区间.)

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 5005, p = (int)1e9 + 7;

int qpow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1)
			ans = (long long)ans * a % p;
		
		b >>= 1;
		a = (long long)a * a % p;
	}
	return ans;
}

int inv[maxn];
int a[maxn], f[maxn][maxn], dp[maxn];

int main() {

	int n, m;
	scanf("%d%d", &n, &m);
	
	inv[1] = 1;
	for (int i = 2; i <= n; i++)
		inv[i] = (long long)(p - p / i) * inv[p % i] % p;

	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		a[i] = m - a[i] + 1;
	}

	if (any_of(a + 1, a + n + 1, [] (int x) {return x <= 0;})) {
		printf("0\n");
		return 0;
	}

	for (int i = n - 1; i; i--)
		a[i] = min(a[i], a[i + 1]);

	// b_i >= b_{i - 1} && b_i <= a_i
	// 我们可以假设 b_i <= a_i 是必定被满足的，然后对 bi 非严格递增的条件进行容斥，枚举某一段是严格递减的
	// 如果 [j, i] 严格递减，显然它们都 <= a_j，所以这个区间的方案数是 {a_j \choose i - j + 1}
	// 如果 i 是合法的，直接一个个转移即可，因为这一部分的转移和区间长度没有关系

	for (int i = 1; i <= n; i++) {
		f[i][0] = 1;

		for (int j = 1; j <= n - i + 1 && j <= a[i]; j++)
			f[i][j] = (long long)f[i][j - 1] * (a[i] - j + 1) % p * inv[j] % p;
	}

	dp[0] = 1;

	for (int i = 1; i <= n; i++) {
		dp[i] = (long long)dp[i - 1] * a[i] % p;

		for (int j = 1; j < i; j++) {
			int tmp = (long long)dp[j - 1] * f[j][i - j + 1] % p;

			if ((i - j) % 2)
				tmp = p - tmp;
			
			dp[i] = (dp[i] + tmp) % p;
		}
	}

	printf("%d\n", dp[n]);

	return 0;
}