「NOI2019」机器人 (维护多项式dp值)

「NOI2019」机器人 (维护多项式dp值)

写的时候觉得这个题整个复杂度升天，代码升天，然后发现正解居然可以真的这样模拟。。。

(而且自己拉格朗日不熟练所以就咕咕咕。。。)

Part 35-50

首先是一个简单的区间dp

定义\(dp[l][r][Max]\)为区间\([l,r]\)中最大的数为\(Max\)的方案数

转移上，类似构建笛卡尔树，枚举区间中最大的点\(k\)

由于题目的限制，我们令\(Max_{lson}\leq Val_k<Max_{rson}\)

这样，\(k\)这个点行走的区域就是\([l,k-1],[k+1,r]\)，带入题目的限制即可

复杂度\(O(n^3+n^2 Max)\)

但是由于两边的访问区间极其接近二叉树，所以\(\text{dfs}\)之后可以发现，所需访问的节点完全达不到\(O(n^2)\)，接近\(10n\)

所以直接用dfs，状态前两维标号就可以了

Part100

考虑边界条件\(dp[i][i]\)

可以发现

\(dp[i][i][j]=\left\{ \begin{aligned} 0 && j<L_i \\ 1 && j\in [L_i,R_i] \\ 0 && j>R_i\end{aligned}\right.\)

这是一个分段的0次多项式(??)

转移

\(dp[l][r][Max]\leftarrow dp[l][k-1][1..Max]\cdot dp[k+1][r][1..Max-1]\)

我们知道任何一个\(n\)次多项式的前缀和都可以表示为一个\(n+1\)次多项式

所以可以归纳得到\(dp[i][j][k]\)是一个关于\(k\)的\(j-i\)次的分段多项式

其中分段数显然是\(O(r-l)\)的

那么我们考虑每次合并两个前缀和，然后相乘得到\(dp[i][j][k]\)，再自己进行累和

如何将前缀和转化为多项式？分成\(n\)个\(i^k\)前缀和，然后通过拉格朗日插值法得到

不要问我复杂度是多少，我们都是有梦想的人。。

#include<bits/stdc++.h>
using namespace std;

#define reg register
typedef long long ll;
#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)

#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0,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=310,P=1e9+7;

bool be;

int n;
int L[N],R[N];

typedef vector <int> Poly;
// 多项式计算部分
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
Poly operator * (const Poly a,const Poly b) {
	Poly res(a.size()+b.size()-1);
	rep(i,0,a.size()-1) rep(j,0,b.size()-1) res[i+j]=(res[i+j]+1ll*a[i]*b[j])%P;
	return res;
}
Poly operator + (Poly a,Poly b) {
	if(a.size()<b.size()) swap(a,b);
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
ll Calc(Poly a,int x){ 
	ll res=0;
	for(int i=0,t=1;i<(int)a.size();++i,t=1ll*t*x%P) res=(res+1ll*t*a[i])%P;
	return res;
}

int a[N],b[N];
Poly sik[N],T[N*100];
// sik: sum i^k前缀和系数
int h[N*100],hc;

struct Node{ 
	int L,R,S; Poly V;
	bool operator < (const Node __) const { return L<__.L; }
}Empty;
vector <Node> dp[N][N]; // 存分段的dp函数

Poly PrefixSum(Poly V) {
	Poly res(V.size()+1);
	rep(i,0,V.size()-1) if(V[i]) rep(j,0,sik[i].size()-1) res[j]=(res[j]+1ll*V[i]*sik[i][j])%P;
	return res;
} // 将多项式转化为前缀和

Poly Que(vector <Node> &V,int x){ 
	if(V.rbegin()->R<=x){ Poly temp; temp.pb(V.rbegin()->S); return temp;}
	if(V[0].L>x) { Poly temp(1); return temp; }
	Empty.L=x;
	int p=upper_bound(V.begin(),V.end(),Empty)-V.begin()-1;
	if(V[p].L<=x && V[p].R>x) return V[p].V;
	else { Poly temp(1); return temp; }
} // 找到x对应的多项式分段

int C[N][N];
// x -> x-1
Poly Down(Poly x) {
	rep(i,0,x.size()-1) {
		rep(j,0,i-1) { 
			if((i-j)&1) x[j]-=1ll*x[i]*C[i][j]%P,Mod2(x[j]);
			else x[j]+=1ll*x[i]*C[i][j]%P,Mod1(x[j]);
		}
	}
	return x;
} // 由于右边是-1的前缀和，所以要把x-> x-1，直接二项式定理展开即可

void dfs(int L,int R) {
	if(dp[L][R].size()) return;
	if(L==R+1) {
		Poly tmp; tmp.pb(1);
		dp[L][R].pb((Node){0,1,1,tmp});
		return;
	}
	if(L==R) {
		int l=::L[L],r=::R[L];
		Poly tmp; tmp.pb(P-l+1); tmp.pb(1);
		dp[L][R].pb((Node){l,r,r-l,tmp});
		return;
	}
	int mid=(L+R)>>1;
	hc=0;
	rep(i,max(L,mid-2),min(R,mid+2)) if(abs((i-L)-(R-i))<=2) dfs(L,i-1),dfs(i+1,R);
	rep(i,max(L,mid-2),min(R,mid+2)) if(abs((i-L)-(R-i))<=2) {
		h[++hc]=::L[i],h[++hc]=::R[i];
		for(Node p:dp[L][i-1]) {
			h[++hc]=p.L;
			h[++hc]=p.R;
		}
		for(Node p:dp[i+1][R]) {
			h[++hc]=p.L+1;
			h[++hc]=p.R+1;
		}
	}
	sort(h+1,h+hc+1),hc=unique(h+1,h+hc+1)-h-1;
    // 预处理分段
	rep(i,1,hc) T[i].clear();
	rep(i,max(L,mid-2),min(R,mid+2)) 
        if(abs((i-L)-(R-i))<=2) 
            rep(j,1,hc-1) if(::L[i]<=h[j] && h[j]<::R[i]) 
            	T[j]=T[j]+Que(dp[L][i-1],h[j])*Down(Que(dp[i+1][R],h[j]-1));
    // 转移时相乘即可
	int lst=0;
	rep(i,1,hc-1) if(T[i].size()) {
		T[i]=PrefixSum(T[i]);
		T[i][0]-=Calc(T[i],h[i]-1),Mod2(T[i][0]);
		T[i][0]+=lst,Mod1(T[i][0]);
		lst=Calc(T[i],h[i+1]-1);
		while(T[i].size() && *T[i].rbegin()==0) T[i].pop_back();
		if(!T[i].size()) continue; // 小剪枝
		dp[L][R].pb((Node){h[i],h[i+1],lst,T[i]});
        // 累成前缀和
	}
	if(!dp[L][R].size()) {
		Poly temp(1);
		dp[L][R].pb((Node){0,1,0,temp});
	} // 如果出现dp值为空要特判
	return;
}


Poly Lang(int n,int *a,int *b){
	Poly res(n),c(n+1),tmp;
	c[0]=1;
	//  c = (x-a[i])
	rep(i,0,n-1) {
		drep(j,i+1,0) {
			c[j]=(-1ll*c[j]*a[i]%P+(j?c[j-1]:0)+P)%P;
		}
	}
	rep(i,0,n-1) {
		ll t=1;
		rep(j,0,n-1) if(i!=j) t=t*(a[i]-a[j])%P;
		t=(qpow(t)*b[i]%P+P)%P;
		tmp=c;
		// c/(x-a[i])
		drep(j,n-1,0) {
			res[j]=(res[j]+t*tmp[j+1])%P;
			tmp[j]=(tmp[j]+1ll*a[i]*tmp[j+1])%P;
		}
	}
	return res;
} // 拉格朗日插值

int main(){
	freopen("robot.in","r",stdin),freopen("robot.out","w",stdout);
	n=rd();
	rep(i,0,n+2) rep(j,C[i][0]=1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P; // 预处理组合数
	rep(i,0,n+2){
		ll s=0;
		rep(j,1,i+1) {
			s+=qpow(j,i),Mod1(s);
			a[j]=j,b[j]=s;
		}
		sik[i]=Lang(i+2,a,b);
	}
	rep(i,1,n) L[i]=rd(),R[i]=rd()+1;
	dfs(1,n);
	printf("%d\n",dp[1][n].rbegin()->S);
}