[校内训练20161216] T2 版本管理git

[校内训练20161216] T2 版本管理git

时间限制:2000MS      内存限制:1048576KB

难度:\(7.0\)

  • 题目描述

在工程的开发中,我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的:刚开始只有一个版本 \(0\),表示最初始的情况,也就是空的项目;接下来一个用户可以对某一个版本 \(p\) 的项目进行修改,得到一个新的版本 \(i\)。这样,一个工程就产生了许多不同的版本,而管理员可以选择一些优秀的,将其合并到主版本中。

\(F\) 公司有一个项目 \(U\),这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改,其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。

作为项目的总负责人,你希望对这些版本进行评价。对一个字符串 \(S\),称串 \(S\) 是串 \(T\) 的超前缀,当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串,如若 \(T = abcd\),则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\),当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀,且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀(定义空串的 \(kitty\) 长度为 \(0\))。你需要做的就是对每一个版本求出其的 \(kitty\) 长度(设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\))。

在实际运营中,有两种情况,我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中, 你可以等候开发者进行所有修改后,再进行计算;但在 \(k = 1\) 的情况中,开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度,你需要实时计算出每个版本的 \(kitty\) 长度。

  • 输入格式

第一行包含三个整数 \(n,m,k\)。

接下来 \(n\) 行,其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\),其中:

如果 \(k = 0\) ,则 \(p_i = p^{′}_{i}\),\(c_i = c^{′}_{i}\);

如果 \(k = 1\),则 \(p_i = p^{′}_{i} \oplus kitty(i …