题解：P10326 自由（Freedom）

· · 题解

测试点 1

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

测试点 2,3

都是 \texttt{K} 开头，数据里 m=n^2，是完全图。不仅如此，每条边的边权还是一样的。

那就不用考虑边不边的了。题意转化成求所有值域在 [1,n] 和为 V 的序列的权值和，若序列长为 t 则序列的权值为 c^{t-1}。在测试点 2,3 里 c=3,7。

看着就很可以 dp 啊！设 dp(i) 表示点权和为 i 的答案乘 c，转移为 dp(t)=\sum\limits_{i=1}^nc\times dp(t-a_i)。这是一个常系数线性齐次递推，用普通方法做是 O(W\log W\log V) 的，其中 W 是 a_i 的最大值。可以通过这两个点。

测试点 4

还是边权相同的完全图，但这次 W 很大，普通的常系数线性齐次递推跑不过。这里 c=7。

但是观察点权，你发现只有两个值，因此转移形如 dp(t)=r\times dp(t-1)+s\times dp(t-x)，其中 r=42c=294,s=38c=266,x=537653823。

考虑组合意义，把 i 向 i+x 连边权为 s 的边，向 i+1 连边权为 r 的边，则要求从 0 到 v 所有路径边权积的和，最后乘上 \dfrac 1 c，因为我们把第一个点也当连边算了，但其实它没连。

发现路径边权积只取决于经过了多少条 i\to i+x 的边。我们枚举经过的边数 t，由于 xt\le V，有 t=O(\dfrac V x)。

对于一个 t，我们可以求出经过 i\to i+1 的边数为 V-tx，则路径个数为 \dbinom{V-tx+t}{t}，权值为 r^{V-tx}s^t。

所以答案为 \dfrac 1 c\sum\limits_{t=0}^{\lfloor\frac V x\rfloor}\dbinom{V-tx+t}{t}r^{V-tx}s^t。暴力计算组合数，复杂度为 O\left(\left(\dfrac V x\right)^2\right)，大概是 20000^2，能过。

Case 5

进入 \texttt{MP} 开头的点。发现点权全部都是 1，于是询问的其实是经过 V 个点的路径权值和。

这是一个非常经典的模型。设 dp(i,j) 表示经过 i 个点目前到 j 的路径权值和，转移形如乘一个矩阵，可以矩阵快速幂。

值得注意的是，这个矩阵是邻接矩阵，记为 A。

最后答案为所有 dp(V,*) 的和，初始 dp(1,*)=1。故答案为 A^{V-1} 所有元素的和。

这个点 n 很小，直接暴力矩阵乘法 O(n^3\log V) 可过。

Case 6

观察图的性质，发现前 n 条边是 1 连出去的，后 n-1 条边从 i 连向 i+1 且边权为 1。

所以说邻接矩阵形如（没写出的元素均为 0）：

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)。

先来列递推方程。考虑每个点向外走到哪个点，可以列出：

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}} #### 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)。