P6144 [USACO20FEB]Help Yourself P
将线段按照了 \(r\) 排序，设右端点为 \(r\) 的答案为 \(f_r\)，发现这样转移非常困难。
\(\color{yellow}{\bigstar\texttt{Trick}}\)：区间覆盖的题要按照左端点排序，记右端点为 \(r\) 时的答案为 \(f_r\)。
考虑 \(k=1\) 时怎么做，加入一条线段，
- 对于 \([1,l-1]\) 的合法 \(f_i\)，可以连通块个数加上 \(1\) 累加到 \(f_r\)；
- 对于 \([l,r]\) 的 \(f_i\) 直接累加到 \(f_r\)；
- 对于 \([r+1,n]\) 的 \(f_i\) 数值乘上 \(2\) 后累加到 \(f_i\)，这条线段可以选或不选。
对于 \(k>1\)，维护答案的 \([0,k]\) 次的所有值 ，\(x^k\rightarrow (x+1)^k=\sum_{i=0}^k\binom{k}{i}x^i\)，预处理系数后 \(\mathcal{O(k)}\) 加即可。
#define Maxn 100005
#define Maxk 11
#define mod 1000000007
int n,m,k;
int C[Maxk][Maxk];
inline int MOD(int x){ return (x>=mod)?(x-mod):x; }
struct Seg
{
int l,r;
Seg(int L=0,int R=0):l(L),r(R){}
bool friend operator < (Seg x,Seg y) { return x.l<y.l; }
}s[Maxn];
struct TREE
{
int a[Maxk],muti;
TREE(){ memset(a,0,sizeof(a)),muti=1; }
inline friend TREE operator + (TREE x,TREE y)
{
TREE ret;
for(int i=0;i<=k;i++) ret.a[i]=MOD(x.a[i]+y.a[i]);
return ret;
}
inline void Push(int x)
{ for(int i=0;i<=k;i++) a[i]=1ll*a[i]*x%mod; muti=1ll*muti*x%mod; }
};
TREE tree[Maxn<<3],adx;
inline void pushdown(int p)
{
if(tree[p].muti>1)
tree[p<<1].Push(tree[p].muti),tree[p<<1|1].Push(tree[p].muti),
tree[p].muti=1;
}
void change(int p,int nl,int nr,int x)
{
if(nl==nr) { tree[p]=adx; return; }
int mid=(nl+nr)>>1; pushdown(p);
if(mid>=x) change(p<<1,nl,mid,x);
else change(p<<1|1,mid+1,nr,x);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
void Times(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) { tree[p].Push(2); return; }
int mid=(nl+nr)>>1; pushdown(p);
if(mid>=l) Times(p<<1,nl,mid,l,r);
if(mid<r) Times(p<<1|1,mid+1,nr,l,r);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
TREE query(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) return tree[p];
int mid=(nl+nr)>>1; pushdown(p);
if(mid>=l && mid<r)
return query(p<<1,nl,mid,l,r)+query(p<<1|1,mid+1,nr,l,r);
else if(mid<r) return query(p<<1|1,mid+1,nr,l,r);
else return query(p<<1,nl,mid,l,r);
}
int main()
{
C[0][0]=1;
for(int i=1;i<=10;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
n=rd(),k=rd(),m=n<<1;
for(int i=1,l,r;i<=n;i++) l=rd(),r=rd(),s[i]=Seg(l,r);
sort(s+1,s+n+1); adx=TREE(),adx.a[0]=1;
change(1,0,m,0);
for(int T=1;T<=n;T++)
{
Times(1,0,m,s[T].r+1,m);
adx=query(1,0,m,0,s[T].l-1);
TREE ret;
for(int i=0;i<=k;i++) for(int j=0;j<=i;j++)
(ret.a[i]+=1ll*C[i][j]*adx.a[j]%mod)%=mod;
adx=ret+query(1,0,m,s[T].l,s[T].r);
change(1,0,m,s[T].r);
}
printf("%d\n",tree[1].a[k]);
return 0;
}