GitHub 源文件 Markdown English

多类配对的 DNA 双链计数

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事

把双链无环 DNA 的计数模型推广到多种互补字母。每次询问可以使用不同的长度、互补对种类数和取模参数。

形式化问题描述

一次询问给出 \(N,K,P\) .字母表由 \(K\) 对不同的字母 \(a_1,b_1,\ldots,a_K,b_K\) 组成，共 \(2K\) 种。互补关系为 \(a_i\) 与 \(b_i\) 配对；不同字母对彼此不配对，没有字母与自身配对。

一个含 \(N\) 个字母对的双链结构由长度为 \(N\) 的字符串 \(s\) 表示。反向互补操作为

\[ R(s)=\overline{s_N}\,\overline{s_{N-1}}\cdots\overline{s_1} \]

两个字符串表示相同结构，当且仅当它们相等，或者其中一个是另一个的反向互补串。字母种类有固定标记；不同互补对之间不另作重命名等同。

求结构种类数对 \(P\) 取模后的非负最小剩余。共有 \(M\) 次询问，最终输出全部余数的按位异或。

输入格式

第一行整数 \(M\) .接下来 \(M\) 行，每行三个整数 \(N,K,P\) .字母本身不需要输入，配对规则如上定义。

输出格式

输出一行一个非负整数，表示每次询问先按各自的 \(P\) 取模后，所有结果的按位异或。

样例

样例 1

输入

3
1 1 100
2 1 100
3 2 100

输出

34

样例 2

输入

4
2 2 2
4 1 4
4 2 1
1 5 7

输出

7

样例 3

输入

1
2 3 6

输出

3

样例解释

第一组的三个计数为 \(1,3,32\) ，均小于各自模数，异或为 \(34\) .第二组的四个余数为 \(0,2,0,5\) ，异或为七。模数为一时，余数总是零。

第三组有六种字母，长度为二，结构种类数为 \(21\) ，模六得到三。

图中用 A 、T 表示任意一对互补字母。箭头表示反向互补，左右两图各形成一个等价类。

数据范围与保证

对所有数据，\(1\le M\le500000\) ，\(1\le N,K,P\le10^9\) .\(P\) 可以为一、偶数或合数，询问可重复。

分值比例	额外条件
100%	无额外条件