题目传送门
题目大意： 在数轴上有 n n n 条线段，如果两条线段相交则称其连通，连通块数量的 K K K 次方称为该线段集合的贡献，求这 n n n 条线段的所有子集（一共 2 n 2^n 2n 个）的贡献之和。
这个 K K K 次方不好处理，按套路用第二类斯特林数转化一下： ∑ P ∈ S a n s ( P ) K = ∑ i = 1 K i ! S ( K , i ) ∑ P ∈ S C a n s ( P ) i \sum_{P\in S}ans(P)^K=\sum_{i=1}^Ki!S(K,i)\sum_{P\in S}C_{ans(P)}^i P∈S∑ans(P)K=i=1∑Ki!S(K,i)P∈S∑Cans(P)i
令 f [ i ] [ j ] f[i][j] f[i][j] 表示子集中最右的端点在 i i i 位置时的 ∑ C a n s ( P ) j \sum C_{ans(P)}^j ∑Cans(P)j，将线段按左端点从小到大排序，考虑每条线段的贡献。
对于一条线段 [ l , r ] [l,r] [l,r]，贡献有三类：
对于 i ∈ [ 1 , l ) i\in [1,l) i∈[1,l)，加上 [ l , r ] [l,r] [l,r] 后连通块数会 + 1 +1 +1，用 C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} Cnm=Cn−1m+Cn−1m−1 来求出新增的贡献，即用 f [ i ] [ j ] + f [ i ] [ j − 1 ] f[i][j]+f[i][j-1] f[i][j]+f[i][j−1] 来贡献 f [ r ] [ j ] f[r][j] f[r][j]。对于 i ∈ [ l , r ] i\in [l,r] i∈[l,r]，加上 [ l , r ] [l,r] [l,r] 后连通块数不变，直接用 f [ i ] [ j ] f[i][j] f[i][j] 来贡献 f [ r ] [ j ] f[r][j] f[r][j] 即可。对于 i ∈ ( r , n ] i\in (r,n] i∈(r,n]，注意到如果 f [ i ] [ j ] > 0 f[i][j]>0 f[i][j]>0，那么一定存在一条线段 [ x , y ] [x,y] [x,y] 满足 x ≤ l , y > r x\leq l,y>r x≤l,y>r，即 [ l , r ] [l,r] [l,r] 是被 [ x , y ] [x,y] [x,y] 包含的，那么 [ l , r ] [l,r] [l,r] 选不选无所谓，令 f [ i ] [ j ] f[i][j] f[i][j] 乘以 2 2 2 即可。用线段树维护一下 f f f 就做完了，代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 100010 #define mod 1000000007 int n,k; struct seg{int l,r;}a[maxn]; bool cmp(seg x,seg y){return x.l<y.l;} void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);} int add(int x){return x>=mod?x-mod:x;} #define zuo ch[0] #define you ch[1] struct node{ int l,r,mid,c[11],lazy;node *ch[2]; node(int x,int y):l(x),r(y),mid(l+r>>1),lazy(1){ for(int i=0;i<=k;i++)c[i]=0; if(x<y){ zuo=new node(l,mid); you=new node(mid+1,r); }else zuo=you=NULL; } void update(int x){ lazy=1ll*lazy*x%mod; for(int i=0;i<=k;i++)c[i]=1ll*c[i]*x%mod; } void pushdown(){ if(lazy!=1){ if(zuo)zuo->update(lazy),you->update(lazy); lazy=1; } } void change(int x,int *w){ pushdown(); for(int i=0;i<=k;i++)add(c[i],w[i]); if(l<r)ch[x>=mid+1]->change(x,w); } void change(int x,int y,int z){ pushdown(); if(l==x&&r==y)return update(z); if(y<=mid)zuo->change(x,y,z); else if(x>=mid+1)you->change(x,y,z); else zuo->change(x,mid,z),you->change(mid+1,y,z); for(int i=0;i<=k;i++)c[i]=add(zuo->c[i]+you->c[i]); } void ask(int x,int y,int *w){ pushdown(); if(l==x&&r==y){ for(int i=0;i<=k;i++)add(w[i],c[i]); return; } if(y<=mid)zuo->ask(x,y,w); else if(x>=mid+1)you->ask(x,y,w); else zuo->ask(x,mid,w),you->ask(mid+1,y,w); } }*root=NULL; int tmp[11],d[11]; int S[11][11],ans=0; int main() { scanf("%d %d",&n,&k); for(int i=1;i<=n;i++)scanf("%d %d",&a[i].l,&a[i].r); sort(a+1,a+n+1,cmp); root=new node(0,2*n); tmp[0]=1;root->change(0,tmp); for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++)d[j]=0;root->ask(0,a[i].l-1,d); tmp[0]=d[0];for(int i=1;i<=k;i++)tmp[i]=add(d[i]+d[i-1]); for(int j=0;j<=k;j++)d[j]=0;root->ask(a[i].l,a[i].r,d); for(int i=0;i<=k;i++)add(tmp[i],d[i]); if(a[i].r<2*n)root->change(a[i].r+1,2*n,2); root->change(a[i].r,tmp); } S[0][0]=1; for(int i=1;i<=k;i++){ for(int j=1;j<=i;j++){ S[i][j]=add(S[i-1][j-1]+1ll*j*S[i-1][j]%mod); } } int fac=1; for(int i=1;i<=k;i++){ fac=1ll*fac*i%mod; add(ans,1ll*fac*S[k][i]%mod*root->c[i]%mod); } printf("%d",ans); }