ZR省选集训Day5

首先确定路径后可以直接得到答案

分成两种状态,一个点是 $dp_{i,j}$ 表示到i这个点的w是j

然后还有一种是 $dp2_{j}$ 表示到点 $j$ 然后

$i,j->j,k$ 是考虑在j的地方加满的最小代价

bitset优化LCS可以做到30qaq

把dp的

转移画成一张网格图,那么我们每次就是询问两点间最长路

分治,取一排中间点,算出左边所有点到他所有点的最长度,右边所有点到他所有点的最长路

然后两边加起来取max即可

算最长路可以拓扑排序类似的

然后一直做到底部 $T(n)=2T(n/2)+n^{1.5}$

$O(S^3+qS)$

都是横着切会T我们要保证矩形大小是根号级别,所以要横竖交替的切,类似于KDT的

因为边界上的点可能很多

正解,因为分治,我们要算中间一排点对于下面一排点最短路

每次都算是 $O(n^3)$

相当于问

凯莱定理

n个连通块连成生成树的方案数

$\prod x_i (\sum x_i)^{r-2}$

非树边怎么连接?总的边减去内部边减去(r-1)跳树边是非树边的方案

这些都是要大于m的,所以有(k-m-1)的染色方案

还有一个 $\prod dp_{x_i,m-1}$

类似于背包,每次选一个就放入一个qwq

这个东西是关于m的多项式,次数和边数相关,求出权值小的部分插值即可

这个就是 $n^2$ 次多项式插个值即可

自主整理:

我们有一个结论:在一个点的决策要么加满油要么加油到能到下一个点

因为如果路径固定,这个点能到达下一个更便宜的就是直接到达,否则就是挣扎到下一个点

$dp_{i,j}$ 表示我们目前从i加满油到了j的最小代价

$f_{i}$ 表示我们到达i油箱刚好为0的最小代价

转移考虑对于下一个点j我们怎么去转移

$dp_{i,j}->dp_{j,k}$

此时转移系数是 $c_j*(w-cst(i,j))+dp_{i,j}$

满足条件是 $cst(j,k)<=w$

显然是可以直接按照某一维度排序

二分所有合法决策点

取个后缀最小值进行转移的

$dp_{i,j}->f_{k}$

此时我们需要 $cst(j,k)-(W-dis(i,j))$ 的额外油量QAQ

也就是说转移系数是 $max(cst(j,k)-(W-dis(i,j)),0)*c_j+dp_{i,j}$

我们固定一个j,然后对于这一整行的i,可以按照类似于第一维加第二维排序,也就是保证存在一个分界点,前面的都取右边,后面的都取左边,那么对于一个k二分出分界,然后对于这两个取前缀max后缀max即可

$f_i->f_k$

观察到这样的转移很少,我们直接枚举即可

$f_i->dp_{i,k}$

此时我们也相当于要直接加满

这个转移的系数和之前是一样的,同样的维护方式即可

zhq&tsx的做法:

先猜出上面的结论

会发现一个点出发本质不同的有用的油数只有 $O(n)$ 个

那么我们记录这些油量,然后考虑怎么转移,对于固定的油量状态,我们只向固定的点数转移

相当于 $dis_{i,j,k}$ 表示经过了i层,然后当前在点j,手上有的油量为k,如果 $k=dis(j,p)$ ,我们只想p转移

否则手上的油量就是 $w-dis(i,p)$ ,也就是说我们这个状态相当于从一个 $dis_{i-1,p,w}$ 转移而来的(第一种)

然后最后的时候我们对于所有的油量状态都向其后转移即可....就是新买入油,然后搞前缀最小值魔术

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 7;
#define ll long long
struct pt {
	int val, id;
	pt(int val = 0, int id = 0): val(val), id(id) {};
	bool operator<(const pt &x)const {
		return val < x.val;
	}
} p[MAXN][MAXN];

int n, m, W, a[MAXN][2], c[MAXN], rp[MAXN][MAXN], len[MAXN];
ll dis[12][MAXN][MAXN];

inline int F(int x) {
	return x > 0 ? x : -x;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d%d", &a[i][0], &a[i][1], &c[i]);
	}
	scanf("%d%d", &W, &m);
	for(int i = 1; i <= n; ++i) {
		int tt = 0;
		for(int j = 1; j <= n; ++j) {
			if(i == j)continue;
			int q = F(a[i][0] - a[j][0]) + F(a[i][1] - a[j][1]);
			if(q <= W) {
				p[i][++tt] = pt(W - q, j);
				p[i][++tt] = pt(q, -j);
			}
		}
		sort(p[i] + 1, p[i] + tt + 1);
		p[i][tt + 1] = pt(W, 0);
		len[i] = tt + 1;
		for(int j = 1; j <= tt; ++j) {
			if(p[i][j].id > 0) {
				rp[i][p[i][j].id] = j;
				//相当于建立映射,就是对于一个权值为x的向一个点的映射这样子qwq
			}
		}
	}
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	dis[0][1][0] = 0;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			ll mn = 1e18;
			for(int k = 0; k <= len[j]; ++k) {
				mn = min(mn, dis[i - 1][j][k] - 1ll * p[j][k].val * c[j]);//选啊
				dis[i][j][k] = min(dis[i][j][k], mn + 1ll * p[j][k].val * c[j]);
			}
		}
		for(int j = 1; j <= n; ++j) {
			for(int k = 0; k <= len[j]; ++k) {
				int u = p[j][k].id;
				if(u < 0)dis[i][-u][0] = min(dis[i][-u][0], dis[i][j][k]);
				if(u > 0)dis[i][j][k] = min(dis[i][j][k], dis[i][u][len[u]]);
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i <= m; ++i) {
		for(int j = 0; j <= len[2]; ++j) {
			ans = min(ans, dis[i][2][j]);
		}
	}
	if(ans > 1e15)puts("-1");
	else printf("%lld\n", ans);
	return 0;
}

$F_{n,m}$ 表示n个点的完全图,最小生成树上的边只赋予 $\leq m$ 的权值,其他边取值 $[1,k]$ ,然后他连成唯一生成树的方案数

这个咋求呢?考虑暴力dp,我们枚举n个点的连通图被分成几块,分成大小怎样的几块,然后这几块之间赋予一个权值m乘起来

那么也就是说我们的转移方法是一个整数划分.....整数划分??艹,背包可以实现如此重任

系数:

首先对于 $x_1...x_r$ 这些连通块,我们全局钦定1为根,然后钦定每个连通块中编号最小的为根,拉起一棵树,其他节点的编号任意分配,这样做的系数是多重组合数

$\binom{n-1}{x_1-1,x_2-1,x_3-1,x_4-1.....}$

注意到我们钦定每个先拿走当前序列中最小元素就相当于给每个盒子一个性质,使得我们的球无论怎么变都是一样的

其他非树边的个数就是 $u=\binom{n}{2}-\sum \binom{x_i}{2} - r+ 1$ ,这个比较显然,把这个直接上 $(k-m)^u$ 即可

然后树边的连法一共有 $(\prod x_i)n^{r-2}$ ,这个是卡莱定理,证明如下

$F(x_i,k-1)$

背包这个东西即可,背包的复杂度就是 $O(n^5)$

这个证明仔细品一品说的就是对于一个给定的prufer序列,我们还原他为树的时候,钦定每个连通块只选择一个点,然后会发现因为我们每次都会删掉一个连通块中点,删掉的那个有 $x_i$ 的方案,而你又会发现每次选择都会带来一整个连通块移除,所以每次都会乘上不同连通块大小

$u=\binom{n}{2}-\sum\binom{x_i}{2}-r+1$

$\binom{n-1}{x_1-1,x_2-1,x_3-1,x_4-1.....}$

$(k-m)^u$

$\prod x_i n^{r-2}$

$F(x_i,k-1)$

观察一下每次我们变化的是

k-m的次数,减少组合数+1

内层组合数,每次多除一个阶乘即可

乘上一个系数 $x_i$ 和 $n$ 最后除掉

因为我们每次背包的时候,对于不同的 $i,j$ ,系数是完全不一样的,所以要重新预处理QAQ不能直接从前面的完全背包

//我竟然T了??
//d j q 的 加 护
//自 带 1 / 2 常 数
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXM = 2507;
const int MAXN = 55;
ll fac[MAXM], ifac[MAXM], inv[MAXM], f[MAXM][MAXN], dp[MAXM];
int m, V, P, n;
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}
inline void init() {
	fac[0] = ifac[0] = 1;
	for(int i = 1; i <= m; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[m] = ksm(fac[m], P - 2);
	for(int i = m - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	for(int i = 1; i <= m; ++i) {
		inv[i] = ifac[i] * fac[i - 1] % P;
		inv[i] = inv[i] * inv[i] % P;
	}
	return;
}
ll ans = 0, y[MAXM], wp[MAXM], wpx[MAXM];
inline void chazhi(int x) {
	//m+1个点值?
	for(int i = 1; i <= m; ++i) {
		ll tmp = y[i];
		for(int j = 1; j <= m; ++j) {
			if(i == j)continue;
			tmp = tmp * (x - j) % P * ksm(i - j, P - 2) % P;
		}
		tmp = (tmp + P) % P;
		add(ans, tmp);
	}
	printf("%lld\n", ans);
	return;
}
inline void solve() {
	f[0][1] = 1;
	for(int i = 1; i <= min(m, V - 1); ++i) {
		for(int j = 1; j <= n; ++j) {
			wpx[j] = ksm(V - i, P - j * (j - 1) / 2 - 2);
		}
		for(int j = 1; j <= n; ++j) {
			//这里预处理这个pw的系数!
			for(int k = 1; k <= j; ++k) {
				wp[k] = f[i - 1][k] * k % P * wpx[k] % P * ifac[k - 1] % P * j % P;
				// printf("%d %d %d %lld ? %lld\n", i, j, k, wp[k], wpx[k]);
				//每次多出一个k,多出一个n,多出一个1/(k-1)!,还有??qwq和前一项系数
				//就是物品/yun
			}
			for(int l = 1; l <= j; ++l)dp[l] = 0;
			dp[0] = 1;
			for(int l = 1; l <= j; ++l) {
				for(int p = 1; p <= l; ++p) {
					add(dp[l], dp[l - p] * wp[p] % P * ifac[l - p] % P); //选上一个p吧
					//这个组合数好阴间啊!!
					//你还要(n-a1-a2-a3....)!
					//最后一步还要有n!...哭了
				}
				dp[l] = dp[l] * fac[l - 1] % P;
			}
			f[i][j] = dp[j] * inv[j] % P * ksm(V - i, j * (j - 1) / 2 + 1) % P;
		}
		y[i] = f[i][n];
	}
	//这有什么意思嘛....
	if(V <= m) {
		printf("%lld\n", f[V - 1][n]);
		return ;
	}
	chazhi(V);
	return ;
}
int main() {
	scanf("%d%d%d", &n, &V, &P);
	m = n * (n - 1) / 2 + 1;
	init();
	solve();
	return 0;
}

吐槽一下dls的计树题都要卡常!!!

$n^5$ 但是他带好几十的常数啊/ll

夏晓光(loveJY)的博客

P6242 [模板]线段树3