← 返回题目列表

Codeforces · 2104/G

G. 模 3

中文机器翻译题面 查看原题

当然,您已经遇到过需要输出模 $$$10^9+7$$$、$$$10^9+9$$$ 或 $$$998244353$$$ 答案的问题。但是您是否遇到过必须打印对 $$$3$$$ 取模的答案的问题?

给您一个由 $$$n$$$ 个顶点组成的函数图,编号从 $$$1$$$ 到 $$$n$$$。它是一个有向图,其中每个顶点都有一个出射弧。该图以数组 $$$g_1, g_2, \dots, g_n$$$ 形式给出,其中 $$$g_i$$$ 表示有一条从 $$$i$$$ 到 $$$g_i$$$ 的弧。对于某些顶点,传出弧可能是自循环。

最初,图的所有顶点都用颜色 $$$1$$$ 着色。您可以执行以下操作:选择一个顶点和从 $$$1$$$ 到 $$$k$$$ 的颜色,然后为该顶点以及从该顶点可达的所有顶点着色。您可以执行此操作任意次数(甚至零次)。

您应该处理 $$$q$$$ 查询。该查询由三个整数$$$x$$$、$$$y$$$ 和$$$k$$$ 描述。对于每个查询,您应该:

  • 分配 $$$g_x := y$$$;
  • 然后计算给定值$$$k$$$的不同图形着色的数量(如果这两种着色中至少存在一个顶点着色为不同颜色,则两种着色不同);由于答案可能非常大,请将其打印出来 模 $$$3$$$.

请注意,在每个查询中,图的初始颜色都会重置(每个查询中所有顶点最初的颜色为 $$$1$$$)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$g_1, g_2, \dots, g_n$$$ ($$$1 \le g_i \le n$$$)。

接下来是 $$$q$$$ 行。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$k_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le k_i \le 10^9$$$)。

输出

对于每个查询,打印一个整数 - 给定值 $$$k$$$ 的不同图形着色的数量,以 $$$3$$$ 为模。

示例

输入
复制

4 5
2 3 1 4
4 3 1
2 1 2
3 4 3
4 1 5
2 4 4

输出
复制

1
2
0
2
1

输入
复制

8 10
7 4 6 8 7 7 1 4
1 7 5
2 3 3
8 6 1
3 1 3
7 2 5
5 2 4
2 7 4
4 6 5
5 2 3
4 5 1

输出
复制

1
0
1
0
2
1
1
2
0
1