[ARC108E] Random IS

仔细观察容易想到设 \(f_{l,r,x,y}\) 表示限制了区间 \([l,r]\) 种只能取 \([x,y]\) 中的数期望取多少个，看一下转移发下可能对最终答案有贡献的 \([x,y]\) 只可能是 \([p_{l-1},p_{r+1}]\)

设 \(cnt\) 为区间 \([l,r]\) 内在 \([p_{l-1},p_{r+1}]\) 中的元素个数 我们有:

考虑求和很像二维数点，但是一般的先枚举长度在枚举左端点是做不了的。区间dp还有一种不常用的枚举顺序是左端点从右往左，右端点从左往右枚举。这样每次能固定一个左端点，当前左端点以及每一个右端点开个树状数组即可，求 \(cnt\) 也是一样的。

#include <bits/stdc++.h>

using namespace std;

const int N = 2005, mod = 1e9 + 7;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
	return s * f;
}

inline int power(int a, int b) {
	int t = 1, y = a, k = b;
	while (k) {
		if (k & 1) t = (1ll * t * y) % mod;
		y = (1ll * y * y) % mod;
		k >>= 1;
	} return t;
}

int inv[N], n, p[N], f[N][N];

struct BIT {
	int tree[N];
	inline BIT() { }
	inline void clear() {
		memset(tree, 0, sizeof tree);
	}
	inline void add(int x, int k) {
		++x;
		for (int i = x; i <= n + 2; i += i & -i) {
			tree[i] = (tree[i] + k) % mod;
			if (tree[i] < 0) tree[i] += mod; 
		}
	}
	inline int sum(int x) {
		int res = 0; ++x;
		for (int i = x; i; i -= i & -i) {
			res += tree[i];
			if (res >= mod) res -= mod;
		} return res;
	}
} pre[N];

int main() {
//	freopen("ex_is2.in", "r", stdin);// freopen("is.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++i) p[i] = read();
	p[0] = 0; p[n + 1] = n + 1;
	for (int i = 1; i <= n; ++i) inv[i] = power(i, mod - 2);
	memset(f, 0, sizeof f); BIT cnt, L;
	for (int i = n; i; --i) {
		cnt.clear(); L.clear();
		for (int j = i; j <= n; ++j) { //i-1 j + 1
			cnt.add(p[j], 1);
			L.add(p[j], f[i][j - 1]);
			pre[j + 1].add(p[i], f[i + 1][j]); 
			int s = cnt.sum(p[j + 1]) - cnt.sum(p[i - 1]);
			if (s <= 0) continue;
			f[i][j] = (1ll * inv[s] * (L.sum(p[j + 1]) - L.sum(p[i - 1]) +
			pre[j + 1].sum(p[j + 1]) - pre[j + 1].sum(p[i - 1])) + 1) % mod;
		}
	}
	printf("%d\n", f[1][n]);
	return 0;
}

原文地址：http://www.cnblogs.com/wwlwakioi/p/16849378.html