「KFCOI Round #1」回首

· · 题解

这一次，我还赌你赢。

这里是出题人的题解。

题目大意

给定一张 n 个节点的图。

一共进行 T 次操作。

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

题目解析

对于 40\% 的数据：

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

对于 100\% 的数据：

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

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

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

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

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 (' ');