LOJ#2567. 「APIO2016」划艇

地址：https://loj.ac/problem/2567

看来在组合计数的路上，还有很长一段路要走啊……
首先$a_i,b_i\leq 10^9$，显然$dp$不能和值域有关。

考虑最终的答案，发现答案统计的时候每一个学校只是在分界点之间做前缀和。

考虑$O(n)$的分界点只会把序列分为$O(n)$段，因此不难想到对值域分段并把段数计入$dp$状态。

接下来的问题变成了怎么转移。我们现在用$f(i,j)$表示第$i$个学校派出的船的数量在第$j$段的方案数。

转移我们就可以分类讨论：

1. $i$学校放到了新的一段$j$中，那么可以从所有段数在$j$前的段转移过来。
 2. $i$学校继续放在第$j$段中，此时我们发现如果要转移，需要引入新状态，于是我们设$f(i,j,k)$，其中$k$表示最后的$j$这一段有多少个学校。

加入$k$这一维后，对转移$1$使用前缀和优化。
处理2的转移，我们可以考虑引入组合数。

但是实际上这道题不用那么复杂，正如$linners$大佬所说的，从组合意义考虑有时远比写组合数来的直观。

我们对最后一段的形态考虑。因为必须严格递增，不能有两个学校的出船数一样。我们可以先把$i$学校任意加入第$j$段中，这时的方案数显然事$len-k+1$种。
那么每一个方案被多算了多少次呢？考虑元素位置一样的方案，只是内部组成了不同的排列。因为必须单增，实际上当前的学校只有唯一确定的一个位置合法，而我们的计算导致我们认为$k$个位置都合法，所以这里转移的系数就是$\frac{len-k+1}{k}$了。

这题有点卡常，注意写的时候控制常数。
```
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 505;
const int mod = 1e9 + 7;
const int inf = 0x7fffffff;
int dp[maxn << 1][maxn], L, R;
int n, a[maxn], b[maxn], ans;
int pos[maxn << 1], cnt, len;
LL inv[maxn << 1], sum[maxn << 1];

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

void Add(int & x, const int & a) {
	x += a;if(x > mod) x -= mod;
}

int main() {
	scanf("%d", &n), inv[1] = 1, inv[0] = 1;
	for(register int i = 1; i <= n << 1; ++i)
		inv[i] = fpow(i, mod - 2);
	pos[++cnt] = 0;
	for(register int i = 1; i <= n; ++i) {
		scanf("%d%d", &a[i], &b[i]);
		pos[++cnt] = a[i] - 1, pos[++cnt] = b[i];
	}
	sort(pos + 1, pos + cnt + 1);
	cnt = unique(pos + 1, pos + cnt + 1) - pos - 1;
	pos[cnt + 1] = pos[cnt] + 1, ++cnt;
	dp[0][0] = 1, sum[0] = 1;
	for(register int j = 1; j < cnt; ++j)
		sum[j] = sum[j - 1];
	for(register int i = 1; i <= n; ++i) {
		L = 1, R = cnt;
		while(pos[L] < a[i] - 1) ++L;
		while(pos[R] > b[i]) --R;
		for(register int j = L; j < R; ++j) {
			len = pos[j + 1] - pos[j];
			for(register int k = i; k >= 2; --k) {
				Add(dp[j][k], (dp[j][k - 1] * inv[k] % mod) * (len - k + 1) % mod);
			}
			Add(dp[j][1], sum[j - 1] * len % mod);
		}
		sum[0] = dp[0][0];
		for(register int j = 1; j <= cnt; ++j) {
			sum[j] = sum[j - 1];
			for(register int k = 0; k <= n; ++k)
				sum[j] += dp[j][k];
			sum[j] %= mod;
		}
	}
	printf("%d", sum[cnt - 1] - 1);
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链