【BZOJ 4584】[APIO2016] 赛艇

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4584
数据生成器：http://paste.ubuntu.com/23985797/
神犇题解：http://blog.csdn.net/worldwide_d/article/details/54572626

解题报告

这货如果划艇数量比较科学的话，我们大家都会做$O(n^3)$的$DP$
于是很自然地想到离散化
离散化之后的区间之间的大小很好比较，但同一个区间内的大小不怎么好比较
但仔细想一想，如果我们知道一个离散化之后的区间内有几所学校，那么似乎搞一搞组合数就可以了
于是定义$f[i][j][k]$表示考虑到第$i$个学校，派出数量最多的学校的数量在离散化区间$j$，这个区间内共有$k$个学校的方案数
然后$O(n^3)$的DP就可以啦！

另外，这题要卡常
不要问我是怎么知道的 _(:з」∠)_
似乎用FFT优化的话就不用卡常了？
我们还是安心卡常吧

再另外的话，这题的Discuss灰常赛艇啊！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500+9;
const int M = 1000+9;
const int MOD = 1000000007;

int n,tot,hash[M],f[M][N],h[M][N],g[M],delta[M];
int len[M],l[N],r[N],rev_len[M],rev_n[N],cnt[M]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t & 1) ret = (LL)ret * w % MOD;
	return ret;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) {
		l[i] = hash[++tot] = read();
		r[i] = hash[++tot] = read();
		rev_n[i] = Pow(i, MOD - 2);
	}
	sort(hash+1, hash+1+tot);
	tot = unique(hash+1, hash+1+tot) - hash - 1;
	for (int i=1;i<=n;i++) {
		l[i] = lower_bound(hash+1, hash+1+tot, l[i]) - hash;
		r[i] = lower_bound(hash+1, hash+1+tot, r[i]) - hash;
	}
	for (int i=1;i<=tot;i++) {
		len[i] = hash[i] - hash[i-1];
		rev_len[i] = Pow(len[i], MOD - 2);
	}
	for (int i=1,tmp;i<=n;i++) {
		memcpy(h,f,sizeof(f));
		memset(delta,0,sizeof(delta));
		(f[l[i]][min(n,len[l[i]])] += g[l[i]-1] + 1) %= MOD;
		(delta[l[i]] += g[l[i]-1] + 1) %= MOD;
		for (int k=2,j=l[i],lim=min(n,len[j]),bas=len[j]-1,t=min(n,len[j]);k<=lim;k++,bas--) {
			tmp = ((LL)h[j][k-1] * bas % MOD) * (LL)rev_len[j] % MOD;
			f[j][t] = (f[j][t] + tmp) % MOD;
			delta[j] = (delta[j] + tmp) % MOD;
		}
		for (int j=l[i]+1,LIM=r[i],*a=f[j],*b=h[j];j<=LIM;++j,a=f[j],b=h[j]) {
			(a[1] += (LL)len[j] * (g[j-1] + 1) % MOD) %= MOD; cnt[j]++;
			(delta[j] += (LL)len[j] * (g[j-1] + 1) % MOD) %= MOD;
			for (int k=2,lim=min(cnt[j],len[j]),bas=len[j]-1;k<=lim;k++,bas--) { 
				tmp = ((LL)b[k-1] * bas % MOD) * (LL)rev_n[k] % MOD;
				a[k] = (a[k] + tmp) % MOD;
				delta[j] = (delta[j] + tmp) % MOD;
			}
		}
		for (int i=1,cur=0;i<=tot;i++) {
			cur = (cur + delta[i]) % MOD;
			g[i] = (g[i] + cur) % MOD;
		}
	}	
	printf("%d\n",g[tot]);
	return 0;
}