【省选联考 2022 D1T2】填数（树形DP，拉格朗日插值法）

题面

题解

起初有这么一个想法：枚举路径权值最小值，权值上界不就确定了？

于是，用一个小小小容斥确保最小值等于某个值 l l l ，第一问的答案简单表示为
∑ l ( p ( l , l + K ) − p ( l + 1 , l + K ) ) sum_{l}Big( p(l,l+K)-p(l+1,l+K) Big) l∑(p(l,l+K)−p(l+1,l+K))

其中 p ( l , r ) p(l,r) p(l,r) 表示路径上每个点权值必须在 [ l , r ] [l,r] [l,r] 以内的方案数（第一问答案），类似地，我们可以定义 q ( l , r ) q(l,r) q(l,r) 表示第二问答案。

当我们确定 l , r l,r l,r 后，每个点权的可选区间就可以独立地确定，于是就变成了一个裸的经典的树形DP题，在 l c a lca lca 处算入每条路径的贡献，可以 O ( n ) O(n) O(n) 解决。没什么好说的，代码也很简单。

但是呢，它的值域很恼人，太大了。这时我的想法是，值域可以分成 O ( n ) O(n) O(n) 个不交的区间，这些区间内部的性质都是一样的。具体地，每个区间 [ L , R ] [L,R] [L,R] 需要满足的条件是，当 l l l 从 L L L 增加到 R R R 时， l l l、 l + 1 l+1 l+1 和 l + K l+K l+K 不会跨过任何一个 l i l_i li 和 r i r_i ri 。

这时，每个点权要么在 [ R + 1 , L + K − 1 ] [R+1,L+K-1] [R+1,L+K−1] 之间，要么在 [ L , R ] [L,R] [L,R] 和 [ L + K , R + K ] [L+K,R+K] [L+K,R+K] 这两个边缘区间中，我们发现在边缘区间中的点地位同等，于是有价值的是点权处在两个边缘区间中的点分别的个数。我们令 f [ i ] [ j ] f[i][j] f[i][j] 表示有 i i i 个点权处在 [ L , R ] [L,R] [L,R] 中，有 j j j 个点权处在 [ L + K , R + K ] [L+K,R+K] [L+K,R+K] 中的方案数（不考虑在边缘区间中的具体位置），那么以第一问为例，总的贡献就是
∑ x = L R ( ∑ i + j ≤ n f [ i ] [ j ] ( R − x + 1 ) i ( x − L + 1 ) j ) = ∑ x = L R f ( x ) sum_{x=L}^{R}left(sum_{i+jleq n}f[i][j](R-x+1)^i(x-L+1)^jright)=sum_{x=L}^R f(x) x=L∑R(i+j≤n∑f[i][j](R−x+1)i(x−L+1)j)=x=L∑Rf(x)

好怪哦，但是式子本身不重要，你只需要知道 f ( x ) f(x) f(x) 是关于 x x x 的 O ( n ) O(n) O(n) 次多项式函数就够了！

那么 F ( x ) = ∑ x ′ = L x f ( x ′ ) = ∑ x ′ = L x ( ∑ i + j ≤ n f [ i ] [ j ] ( R − x ′ + 1 ) i ( x ′ − L + 1 ) j ) F(x)=sum_{x'=L}^x f(x')=sum_{x'=L}^x left(sum_{i+jleq n}f[i][j](R-x'+1)^i(x'-L+1)^jright) F(x)=∑x′=Lxf(x′)=∑x′=Lx(∑i+j≤nf[i][j](R−x′+1)i(x′−L+1)j) 也是关于 x x x 的多项式函数，而我们要求的是 F ( R ) F(R) F(R) 。

直接求多项式是 O ( n 4 ∼ n 5 ) O(n^4sim n^5) O(n4∼n5) 的，但是求 f ( x ) f(x) f(x) 的某个点值是 O ( n ) O(n) O(n) 的！（因为 f ( x ) = p ( x , x + K ) − p ( x + 1 , x + K ) f(x)=p(x,x+K)-p(x+1,x+K) f(x)=p(x,x+K)−p(x+1,x+K)）

所以我们可以求出 f ( L ) , f ( L + 1 ) , . . . , f ( L + n ) f(L),f(L+1),...,f(L+n) f(L),f(L+1),...,f(L+n) ，对它们求前缀和得到 F ( L ) , F ( L + 1 ) , . . . , F ( L + n ) F(L),F(L+1),...,F(L+n) F(L),F(L+1),...,F(L+n) ，然后拉格朗日插值法求出 F ( R ) F(R) F(R) 。

对第二问也是类似的。总时间复杂度 O ( n 3 ) O(n^3) O(n3) 。

CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 2005
#define LL long long
#define ENDL putchar('n')
#define lowbit(x) (-(x) & (x))
#define DB double
#define FI first
#define SE second
inline int xchar() {
	static const int maxnn = 1000000;
	static char b[maxnn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxnn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
//#define getchar() xchar()
inline LL read() {
	LL f=1,x=0; int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
	while(s >= '0' && s <= '9') {x=(x<<3)+(x<<1)+(s^48);s = getchar();}
	return f * x;
}
void putpos(LL x) {
	if(!x) return ;
	putpos(x/10); putchar((x%10) ^ 48);
}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x < 0) putchar('-'),x=-x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 1000000007;
const int inv2 = (MOD+1)/2;
int n,m,s,o,k;
int qkpow(int a,int b) {
	int res = 1;
	while(b > 0) {
		if(b & 1) res = res *1ll* a % MOD;
		a = a *1ll* a % MOD; b >>= 1;
	}return res;
}
int hd[MAXN],nx[MAXN],v[MAXN],cne;
void ins(int x,int y) {
	nx[++ cne] = hd[x];v[cne] = y;hd[x] = cne;
}
set st;
int a[MAXN],K;
int l[MAXN],r[MAXN];
int ans1,ans2,L,R,f[MAXN];
int dfs1(int x,int ff) {
	int ll = max(L,l[x]),rr = min(R,r[x]);
	if(ll > rr) ll = rr+1;
	int nw = rr-ll+1,rs = nw,nw2 = (ll+rr)*1ll*nw%MOD * inv2 % MOD;
	f[x] = nw2;
	(ans1 += nw) %= MOD;
	(ans2 += nw2) %= MOD;
	for(int i = hd[x];i;i = nx[i]) {
		if(v[i] != ff) {
			int nm = dfs1(v[i],x);
			(ans2 += f[x]*1ll*nm % MOD) %= MOD;
			(ans2 += rs *1ll* f[v[i]] % MOD) %= MOD;
			(f[x] += (f[v[i]]*1ll*nw%MOD + nw2*1ll*nm%MOD)%MOD) %= MOD;
			(ans1 += nm*1ll*rs%MOD) %= MOD;
			(rs += nm*1ll*nw%MOD) %= MOD;
		}
	}
	return rs;
}
int dfs2(int x,int ff) {
	int ll = max(L+1,l[x]),rr = min(R,r[x]);
	if(ll > rr) ll = rr+1;
	int nw = rr-ll+1,rs = nw,nw2 = (ll+rr)*1ll*nw%MOD * inv2 % MOD;
	f[x] = nw2;
	(ans1 += MOD-nw) %= MOD;
	(ans2 += MOD-nw2) %= MOD;
	for(int i = hd[x];i;i = nx[i]) {
		if(v[i] != ff) {
			int nm = dfs2(v[i],x);
			(ans2 += MOD - f[x]*1ll*nm % MOD) %= MOD;
			(ans2 += MOD - rs *1ll* f[v[i]] % MOD) %= MOD;
			(f[x] += (f[v[i]]*1ll*nw%MOD + nw2*1ll*nm%MOD)%MOD) %= MOD;
			(ans1 += MOD - nm*1ll*rs%MOD) %= MOD;
			(rs += nm*1ll*nw%MOD) %= MOD;
		}
	}
	return rs;
}
pair P_Q(int l,int r) {
	L = l; R = r;
	ans1 = 0; ans2 = 0;
	dfs1(1,0); dfs2(1,0);
	return {ans1,ans2};
}
int xx[MAXN],yy1[MAXN],yy2[MAXN];
int F(int x,int *xx,int *yy,int le) {
	int rs = 0;
	for(int i = 1;i <= le;i ++) {
		int iv = 1,up = yy[i];
		for(int j = 1;j <= le;j ++) {
			if(i == j) continue;
			up = up *1ll* (x+MOD-xx[j]) % MOD;
			iv = iv *1ll* (xx[i]+MOD-xx[j]) % MOD;
		}
		(rs += up*1ll*qkpow(iv,MOD-2) % MOD) %= MOD;
	}
	return rs;
}
int main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n = read();K = read();
	int mx = 0;
	for(int i = 1;i <= n;i ++) {
		l[i] = read(); r[i] = read();
		st.insert(l[i]); st.insert(r[i]+1);
		st.insert(l[i]-1); st.insert(r[i]);
		st.insert(l[i]-K); st.insert(r[i]-K+1);
		mx = max(mx,r[i]);
	}
	for(int i = 1;i < n;i ++) {
		s = read();o = read();
		ins(s,o); ins(o,s);
	}
	for(auto i = st.begin();i != st.end();i ++) {
		if(*i > 0)a[++ m] = *i;
	}
	int as1 = 0,as2 = 0;
	for(int i = 1;i < m;i ++) {
		int ll = a[i],rr = a[i+1]-1;
		if(ll+n >= rr) {
			for(int j = ll;j <= rr;j ++) {
				auto t = P_Q(j,j+K);
				(as1 += t.FI) %= MOD;
				(as2 += t.SE) %= MOD;
			}
		}
		else {
			int sm1 = 0,sm2 = 0;
			for(int j = ll;j <= ll+n;j ++) {
				xx[j-ll+1] = j;
				auto t = P_Q(j,j+K);
				(sm1 += t.FI) %= MOD;
				(sm2 += t.SE) %= MOD;
				yy1[j-ll+1] = sm1;
				yy2[j-ll+1] = sm2;
			}
			(as1 += F(rr,xx,yy1,n+1)) %= MOD;
			(as2 += F(rr,xx,yy2,n+1)) %= MOD;
		}
	}
	AIput(as1,'n');
	AIput(as2,'n');
	return 0;
}

【省选联考 2022 D1T2】填数（树形DP，拉格朗日插值法）

C/C++/C#相关栏目本月热门文章