自动搬运

查看原文

来自洛谷，原作者为

	koukilee 如果...有一天你死了，我也不会忘记你的。除非...这个世界，不再下雨。

搬运于2025-08-24 23:10:04，当前版本为作者最后更新于2025-01-14 20:35:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这一次，我还赌你赢。

这里是出题人的题解。

题目大意

给定一张 $n$ 个节点的图。

一共进行 $T$ 次操作。

每个节点的权值一开始都会乘上 $k_i$，紧接着如果有连向它的点，就加上那些点的权值，否则加上当前进行的操作次数。

题目解析

对于 $40\%$ 的数据：

直接模拟即可，没有任何难度，注意取模的问题，注意这些操作的先后问题。

对于 $100\%$ 的数据：

注意到 $T \le 10^{18}$，此时明显不能暴力模拟。

但是，由于每一次图的形态不会改变，并且每一次每一个点会从哪些点加来权值是固定的。

所以考虑一个并不难的矩阵快速幂。

先预处理出每次操作前的转移矩阵，如下：

$$\begin{matrix} & a_{1_t}&a_{2_t}&a_{3_t}&\dots&i&1\\a_{1_{t - 1}}&k_1&0&0&\dots&0&0\\ a_{2_{t - 1}}&0&k_2&0&\dots&0&0&\\ a_{3_{t - 1}}&0&0&k_3&\dots&0&0\\\dots&0&0&0&\dots&0&0\\ i-1&0&0&0&\dots&1&1\\1&0&0&0&\dots&0&1\\ \end{matrix}$$

接下来，如果 $a,b$ 之间有一条有向边，则将矩阵的 $(a,b)$ 赋值为 $1$。

如果点 $i$ 没有入点，则将 $(n + 1, i),(n + 2,i)$ 赋值为 $1$。

最后直接做矩阵快速幂即可。

代码如下：

  read (n, m, T);

	for (i32 i = 1; i <= n; i++)
		read (Base.mat[i][i]);
	
	for (i32 i = 1; i <= m; i++){
		i64 x, y; read (x, y);
		G[x].push_back (y);
	}
	
	for (i32 i = 1; i <= n; i++) {
		for (auto it : G[i]) 
			in[it]++, Base.mat[i][it] = 1;
	}
	for (i32 i = 1; i <= n; i++)
		if (!in[i])
			Base.mat[n + 1][i] = Base.mat[n + 2][i] = 1;
	Base.mat[n + 1][n + 1] = Base.mat[n + 2][n + 1] = 1;
	Base.mat[n + 2][n + 2] = 1;
	
	F.mat[1][n + 2] = 1;
	
	F = fpow (F, Base, T);
	
	for (i32 i = 1; i <= n; i++)
		print (F.mat[1][i]), putchar (' ');