专栏文章

题解：P10326 自由（Freedom）

llittlez_meow
P10326题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqsu9zx
此快照首次捕获于
2025/12/04 10:10
3 个月前
此快照最后确认于
2025/12/04 10:10
3 个月前
查看原文

测试点 11

发现 n,m,Vn,m,V 都很小，设 dp(i,j)dp(i,j) 表示点权为 ii 结尾为 jj 的路径边权和，转移枚举 jj 的出边。时间复杂度 O(V(n+m))O(V(n+m))。

测试点 2,32,3

都是 K\texttt{K} 开头，数据里 m=n2m=n^2，是完全图。不仅如此，每条边的边权还是一样的。
那就不用考虑边不边的了。题意转化成求所有值域在 [1,n][1,n] 和为 VV 的序列的权值和，若序列长为 tt 则序列的权值为 ct−1c^{t-1}。在测试点 2,32,3 里 c=3,7c=3,7。
看着就很可以 dp 啊！设 dp(i)dp(i) 表示点权和为 ii 的答案乘 cc，转移为 dp(t)=∑i=1nc×dp(t−ai)dp(t)=\sum\limits_{i=1}^nc\times dp(t-a_i)。这是一个常系数线性齐次递推，用普通方法做是 O(Wlog⁡Wlog⁡V)O(W\log W\log V) 的，其中 WW 是 aia_i 的最大值。可以通过这两个点。

测试点 44

还是边权相同的完全图，但这次 WW 很大，普通的常系数线性齐次递推跑不过。这里 c=7c=7。
但是观察点权，你发现只有两个值，因此转移形如 dp(t)=r×dp(t−1)+s×dp(t−x)dp(t)=r\times dp(t-1)+s\times dp(t-x)，其中 r=42c=294,s=38c=266,x=537653823r=42c=294,s=38c=266,x=537653823。
考虑组合意义，把 ii 向 i+xi+x 连边权为 ss 的边，向 i+1i+1 连边权为 rr 的边，则要求从 00 到 vv 所有路径边权积的和，最后乘上 1c\dfrac 1 c，因为我们把第一个点也当连边算了，但其实它没连。
发现路径边权积只取决于经过了多少条 i→i+xi\to i+x 的边。我们枚举经过的边数 tt，由于 xt≤Vxt\le V，有 t=O(Vx)t=O(\dfrac V x)。
对于一个 tt，我们可以求出经过 i→i+1i\to i+1 的边数为 V−txV-tx，则路径个数为 (V−tx+tt)\dbinom{V-tx+t}{t}，权值为 rV−txstr^{V-tx}s^t。
所以答案为 1c∑t=0⌊Vx⌋(V−tx+tt)rV−txst\dfrac 1 c\sum\limits_{t=0}^{\lfloor\frac V x\rfloor}\dbinom{V-tx+t}{t}r^{V-tx}s^t。暴力计算组合数，复杂度为 O((Vx)2)O\left(\left(\dfrac V x\right)^2\right)，大概是 20000220000^2，能过。

Case 55

进入 MP\texttt{MP} 开头的点。发现点权全部都是 11，于是询问的其实是经过 VV 个点的路径权值和。
这是一个非常经典的模型。设 dp(i,j)dp(i,j) 表示经过 ii 个点目前到 jj 的路径权值和，转移形如乘一个矩阵，可以矩阵快速幂。
值得注意的是，这个矩阵是邻接矩阵，记为 AA。
最后答案为所有 dp(V,∗)dp(V,*) 的和，初始 dp(1,∗)=1dp(1,*)=1。故答案为 AV−1A^{V-1} 所有元素的和。
这个点 nn 很小，直接暴力矩阵乘法 O(n3log⁡V)O(n^3\log V) 可过。

Case 66

观察图的性质，发现前 nn 条边是 11 连出去的，后 n−1n-1 条边从 ii 连向 i+1i+1 且边权为 11。
所以说邻接矩阵形如（没写出的元素均为 00）：
w_1 & w_2 & \cdots & w_n \\ 1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \end{bmatrix}$$ 其中 $w_i$ 是 $1\to i$ 的边权。这是一个常系数线性齐次递推的矩阵，也就是说问题变成求 $x_t=\left\{\begin{matrix} 1 & (t<n)\\ \sum\limits_{i=1}^n w_ix_{t-i}& (t\ge n) \end{matrix}\right.$ 的第 $V-1$ 项到 $n+V-2$ 项的和。 为了求区间和，我们想求出前缀和。不妨设 $x$ 的生成函数是 $F(z)$，我们来研究前缀和数列的生成函数 $G(z)$。因为这里有 $x$ 所以形式幂级数用 $z$。 考虑 $[z^i]F(z)$ 的贡献，它会累加到所有 $\ge i$ 的项，相当于这项乘了 $1+z+z^2+\cdots=\dfrac 1{1-z}$。 因此我们有 $G(z)=\dfrac{F(z)}{1-z}$。由于 $F(z)$ 是有理函数，$G(z)$ 也是有理函数，分子分母次数还是 $O(n)$。问题转化为求一个有理函数的高次项系数，这可以用 FFT 优化的 Bostan-Mori 算法解决，时间复杂度 $O(n\log n\log V)$。 当然也可以把 $G(z)$ 重新转回常系数线性齐次递推，虽然稍微有些麻烦，不如直接 Bostan-Mori，而且因为 $n$ 很大你是不能 $O(n^2)$ 的 BM 求递推式的。 #### Case $7$ 这次的 $V$ 超级大，而且 $A^{V-1}$ 是不能用欧拉定理降幂的。 发现输入中每个点连出去的边很少，再仔细看看发现点 $i$ 只会连向 $\ge i$ 的点，而且必然有一条边权为 $i+1$ 的边连向 $i$。 于是得出这是一个主对角线互不相同的上三角矩阵，而且很稀疏。 再结合我们要把指数从矩阵上变到数上来使用欧拉定理，这启发我们相似对角化。 设 $A=P^{-1}\Lambda P$，其中 $\Lambda$ 是把特征值排在主对角线上的对角矩阵，则 $A^{V}=P^{-1}\Lambda^V P$。发现 $P$ 和 $P^{-1}$ 是不随 $V$ 而改变的，因此答案形如 $\sum\limits_{i=1}^n c_i\lambda_i^V$，其中 $c_i$ 是常数。根据欧拉定理，$V$ 可以对 $998244352$ 取模。 写出答案的生成函数为 $F(x)=\sum\limits_{j=0}^{\infty}x^j\sum\limits_{i=1}^n c_i\lambda_i^j$，简单化简得到 $F(x)=\sum\limits_{i=1}^n\dfrac{c_i}{1-\lambda_i x}$。 答案是有理函数，但是带 $c$，还是不好处理。通分一下，分子变成次数小于 $n$ 的多项式 $G(x)$，那么有 $F(x)=\dfrac{G(x)}{\prod\limits_{i=1}^n1-\lambda_i x}$。 由于 $A$ 稀疏，在不带自环的情况下图的路径数很少，可以暴力求出 $F(x)$ 的前 $n$ 项，然后递推出 $G(x)$。这样就可以 Bostan-Mori 了。 #### Case $8$ 给出的图包括 $2i\to 2i-1,2i-1\to 2i,2i-1\to 2i-1，2i-1\to 2i+1$ 这些边，也就是相邻奇数偶数连双向边，相邻奇数从小向大连，奇数连自环。所有边边权为 $1$。 好像没有什么很好直接算的方法，这个图又很规整，那就递推吧。 设 $[x^V]F_i(x)$ 表示从 $2i-1$ 出发长为 $V$ 路径个数（即边权和，因为边权为 $1$）的生成函数，$[x^V]G_i(x)$ 表示从 $2i$ 出发长为 $V$ 路径个数。为了求和，设 $H_i(x)=F_i(x)+G_i(x)$，再设 $t=\dfrac n 2$。 最终答案为 $[x^V]\sum\limits_{i=1}^t H_i(x)$。 先来列递推方程。考虑每个点向外走到哪个点，可以列出： $$\left\{\begin{matrix} F_i(x)=x(1+F_{i-1}(x)+F_i(x)+G_i(x)) \\ G_i(x)=x(1+F_{i}(x)) \end{matrix}\right.$$ 解得 $F_i(x)=\dfrac{x(F_{i-1}(x)+1+x)}{1-x-x^2}$。 代入到 $H_i(x)$，得到 $H_i(x)=\dfrac{xH_{i-1}(x)+2x}{1-x-x^2}$，其中 $H_0(x)=x$。 把 $x$ 看作常数，$H$ 看成数列，则这个递推式是形如 $a_i=pa_{i-1}+q$ 的经典形式，可以化成等比数列求通项。算出来得到： $$H_i(x)=\dfrac{x(x^{i}+\dfrac{2(1-x-x^2)^i-2x^i}{1-2x-x^2})}{(1-x-x^2)^i}$$ 接下来要求 $\sum\limits_{i=1}^t H_i(x)$。把分子拆开，每一项都是等比数列，使用等比数列求和得到： $$\sum\limits_{i=1}^t H_i(x)=\dfrac{1+(n-4) x+(1-2 n) x^{2}+(2-n) x^{3}}{(1-2 x-x^{2})^{2}}+\frac{x^{t+2}(1+x)^{2}}{(1-2 x-x^{2})^{2}(1-x-x^{2})^{t}}$$ $V$ 很大，肯定还是找循环节。但是我不想找循环节，一般循环节都是 $p,p-1,p+1$ 这种东西乘上一个系数，所以我猜循环节是 $5!\times (p-1)p(p+1)$，然后 Bostan-Mori 就行，复杂度 $O(n\log n\log p)$。发现一遍过。 #### Case $9$ 是环。设 $s$ 是点权和，那么肯定是先绕环走 $\lfloor\dfrac V s\rfloor$ 圈，然后再走几步。走的步数可以用双指针求，顺便统计贡献。 要用高精除算圈数，时间复杂度 $O(n+\log V\log n)$。注意圈数在指数上，所以是对 $998244352$ 取模。 #### Case $10$ 这个图只有自环。对于点 $i$，如果 $a_i|V$，则会做出 $w_i^{\frac V{a_i}-1}$ 的贡献，其中 $w_i$ 是 $i\to i$ 的边权。直接计算复杂度 $O(n\log V)$。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...