蜜月日记 Part8

继续蜜月日记。

给模拟赛准备的。

2024/12/12 自由（Freedom）

给定一个 $n$ 个点 $m$ 条边的有向图，定义路径的点权为经过点的点权的和，边权为经过边的边权的积。求点权和为 $V$ 的所有路径的边权和。提交答案。

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

都是 $\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$ 的最大值。可以通过这两个点。

还是边权相同的完全图，但这次 $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$，能过。

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

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

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

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

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

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

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