相关链接
题目传送门：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;
}
