[USACO20FEB]Help Yourself P 题解
可以维护每一个次方的结果然后用二项式定理计算答案。
时间复杂度(O(N imes K imes log_2(n)+N imes K^2))。吐槽一下usaco的评测机，本机(0.8s) 但usaco上TLE，洛谷AC。
/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define int unsigned int
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=100000+20;
const int MAXK=11;
const int MOD=1e9+7;
int n,k;
vector<vector<int> > c;
vector<int> pow2;
vector<int> dp;
void add(int & A,int B){
A+=B;
if(A>=MOD) A-=MOD;
}
void mul(int & A,int B){
A=1ll*A*B%MOD;
}
const int N=1<<17;
struct SEGMENTTREE{
vector<int> tree,addtag,multag;
SEGMENTTREE(){
tree.resize(N+N);
multag.resize(N+N);
addtag.resize(N+N);
}
void pd(int now){
if(multag[now]!=0){
mul(tree[now],pow2[multag[now]]);
if(now<N){
mul(addtag[now<<1],pow2[multag[now]]);
mul(addtag[now<<1|1],pow2[multag[now]]);
multag[now<<1]+=multag[now];
multag[now<<1|1]+=multag[now];
}
}
if(addtag[now]!=0){
add(tree[now],addtag[now]);
if(now<N){
add(addtag[now<<1],addtag[now]);
add(addtag[now<<1|1],addtag[now]);
}
}
multag[now]=0;
addtag[now]=0;
}
int query(int a,int b,int now=1,int l=1,int r=N+1){
pd(now);
if(r<=b&&l>=a){
return tree[now];
}
int mid=(l+r)>>1;
int tmp=0;
if(mid>a) add(tmp,query(a,b,now<<1,l,mid));
if(mid<b) add(tmp,query(a,b,now<<1|1,mid,r));
return tmp;
}
void Mul(int a,int b,int now=1,int l=1,int r=N+1){
if(r<=a||l>=b){
pd(now);
return ;
}
if(r<=b&&l>=a){
multag[now]++;
pd(now);
return;
}
pd(now);
int mid=(l+r)>>1;
Mul(a,b,now<<1,l,mid);
Mul(a,b,now<<1|1,mid,r);
tree[now]=tree[now<<1];
add(tree[now],tree[now<<1|1]);
}
void Add(int a,int val,int now=1,int l=1,int r=N+1){
while(true){
if(l==r-1){
add(addtag[now],val);
}
pd(now);
if(l==r-1) break;
int mid=(l+r)>>1;
if(mid>a){
r=mid;
now<<=1;
}
else{
l=mid;
now=now<<1|1;
}
}
while(now!=1){
pd(now^1);
now>>=1;
tree[now]=tree[now<<1];
add(tree[now],tree[now<<1|1]);
}
}
}valpre[MAXK],dppre[MAXK];
vector<mp> seg;
vector<int> lisan;
signed main(){
scanf("%d%d",&n,&k);
seg.resize(n);
rep(i,n){
seg[i].FIR=read();
seg[i].SEC=read();
}
sort(ALL(seg));
dp.resize(k+1);
pow2.resize(n*k+1);
c=vector<vector<int> > (k+1,vector<int> (k+1,0));
c[0][0]=1;
rb(i,0,k)
rb(j,0,k){
if((!i)&&(!j)) continue;
if(i) c[i][j]=c[i-1][j];
if(j&&i) add(c[i][j],c[i-1][j-1]);
}
pow2[0]=1;
rb(i,1,n*k) pow2[i]=pow2[i-1]<<1,pow2[i]-=(pow2[i]>=MOD? MOD:0);
rep(i,n)
lisan.PB(seg[i].SEC);
sort(ALL(lisan));
rep(i,n){
seg[i].FIR=lower_bound(ALL(lisan),seg[i].FIR)-lisan.begin()+1;
seg[i].SEC=lower_bound(ALL(lisan),seg[i].SEC)-lisan.begin()+1;
}
int val,i,j,z;
for(i=0;i<n;++i){
for(j=0;j<=k;++j){
val=0;
dp[j]=0;
valpre[j].Mul(seg[i].SEC+1,N+1);
dppre[j].Mul(seg[i].SEC+1,N+1);
if(seg[i].FIR!=1)
add(dp[j],valpre[j].query(1,seg[i].FIR));
add(dp[j],1);
if(seg[i].FIR!=seg[i].SEC)
add(dp[j],dppre[j].query(seg[i].FIR,seg[i].SEC));
for(z=0;z<=j;++z){
add(val,1ll*dp[z]*c[j][z]%MOD);
}
valpre[j].Add(seg[i].SEC,val);
dppre[j].Add(seg[i].SEC,dp[j]);
}
}
printf("%d
",dppre[k].query(1,2*n+1));
return 0;
}