[USACO 2020 February Platinum]Help Yourself

真的很套路。。。

考虑将区间$(L_i,R_i)$按照左端点排序，依次考虑每个区间的贡献

令$dp_i$表示当前所有选择的右端点中最大的为$i$时的方案数

加入区间$(L,R)$时

1.所有$i<L$的部分一定会断开成两个区间，转移时个数+1

2.当$i\ge L$时，$dp_i$向$dp_{\max\lbrace R,i\rbrace}$转移，分两类讨论即可

不考虑个数的问题，直接转移是$O(n^2)$的，但是可以用线段树优化到$n\log n$

(比较麻烦，需要实现区间查询，单点修改，区间乘法)

考虑个数$k$次幂，一种暴力的办法是存下$dp_{i,j}$，但是转移会变成$O(n^2\log n)$

对于当前个数为$c$的情况，如果新增一个联通块，即变为$c+1$，答案由$c^k$ 变为$(c+1)^k$

考虑直接用二项式定理展开这个式子，需要记录$c^i(i\in [0,k])$的所有答案，再$O(k^2)$完成+1操作

结合线段树，维护$nk$个值，复杂度为$O(n(k\log n +k^2))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define Mod1(x) ((x>=P)&&(x-=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,P=1e9+7;

int n,k;
Pii A[N];
int C[11][11];
int s[N<<2][11],res[11];
int t[N<<2];
void Up(int p) {
	rep(i,0,k) s[p][i]=s[p<<1][i]+s[p<<1|1][i],Mod1(s[p][i]);
}
void Down(int p) {
	if(t[p]==1) return;
	t[p<<1]=1ll*t[p<<1]*t[p]%P;
	t[p<<1|1]=1ll*t[p<<1|1]*t[p]%P;
	rep(i,0,k) {
		s[p<<1][i]=1ll*s[p<<1][i]*t[p]%P;
		s[p<<1|1][i]=1ll*s[p<<1|1][i]*t[p]%P;
	}
	t[p]=1;
}

void Que(int p,int l,int r,int ql,int qr) {
	if(ql<=l && r<=qr) {
		rep(i,0,k) res[i]+=s[p][i],Mod1(res[i]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Que(p<<1,l,mid,ql,qr);
	if(qr>mid) Que(p<<1|1,mid+1,r,ql,qr);
}

void Upd(int p,int l,int r,int ql,int qr) {
	if(ql<=l && r<=qr) {
		rep(i,0,k) s[p][i]*=2,Mod1(s[p][i]);
		t[p]*=2,Mod1(t[p]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr);
	Up(p);
}
void Upd(int p,int l,int r,int x){
	if(l==r){
		rep(i,0,k) s[p][i]+=res[i],Mod1(s[p][i]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	x<=mid?Upd(p<<1,l,mid,x):Upd(p<<1|1,mid+1,r,x);
	Up(p);
}


int main(){
	n=rd(),k=rd();
	rep(i,1,n) A[i].first=rd(),A[i].second=rd();
	sort(A+1,A+n+1);
	rep(i,1,N*4-1) t[i]=1;
	rep(i,0,k) rep(j,C[i][0]=1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	
	res[0]=1;
	Upd(1,0,n*2,0);

	rep(t,1,n) {
		int l=A[t].first,r=A[t].second;
		Upd(1,0,n*2,r,n*2);
		
		memset(res,0,sizeof res);
		Que(1,0,n*2,0,l-1);
		drep(i,k,0) rep(j,0,i-1) res[i]=(res[i]+1ll*C[i][j]*res[j])%P;
		Upd(1,0,n*2,r);

		memset(res,0,sizeof res);
		Que(1,0,n*2,l,r-1);
		Upd(1,0,n*2,r);
		
	}
	printf("%d\n",s[1][k]);
}