#2261. 「CTSC2017」密钥

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

一个密钥是一个长度为 n=2k+1n = 2k + 1 的字符串,它包含 11 个字母 XXkk 个字母 AAkk 个字母 BB。例如 k=3k = 3 时,BAXABABBAXABAB 就是一个密钥。
如下图所示,可以按顺时针顺序把这 2k+12k+1 个字母排成一个圈:

BAXABAB

kk 个字母 AA 中,有一部分可以定义为「强的」。具体来说,从 XX 出发顺时针走到某个 AA 时,如果途中 AA 的数目严格多于 BB 的数目,则称此字母 AA 为强的。
对于上面的例子来说,顺时针方向从字母 XX 数起第 11 个和第 22 个字母 AA 是强的,而第 33 个字母 AA 不是强的。
一个密钥的特征值就是其中包含的强的字母 AA 的个数。

天才小朋友 KT 给出了一个结论:
假设 kk 个字母 AA 所在的位置已经固定,但是剩下的 kkBB11XX 的位置是未知的。(注意,满足这样要求的密钥一共有 k+1k + 1 个,因为字母 XX 还剩下 k+1k + 1 个可能的位置。)
可以证明:所有这 k+1k + 1 个可能的密钥的特征值是各不相同的,它们恰好为 0,1,2,...,k0,1,2,...,k
下页的图是一个具体的示例,从左到右的四个子图中分别有 33 个,22 个,11 个,00 个字母 AA 是强的。

类似地,如果固定 kk 个字母 BB 的位置,那满足条件的所有 k+1k + 1 个密钥的特征值也各不相同,恰好为 0,1,...,k0,1,...,k

现在你需要解决以下三个问题:

  1. 给定密钥中所有 AA 的位置,当密钥的特征值为 00 时,请问 XX 在哪个位置。
  2. 给定密钥中所有 AA 的位置,当密钥的特征值为 SS 时,请问 XX 在哪个位置。
  3. 给定密钥中所有 BB 的位置,当密钥的特征值为 SS 时,请问 XX 在哪个位置。

注意:字符串的 2k+12k + 1 个字母的位置由 112k+12k + 1 编号。

例子 1

假定 k=3,S=2k = 3,S = 2。那么:
AA 的位置是 {2,4,6}\{2,4,6\} 且特征值为 00 时,XX 的位置在 77
AA 的位置是 {2,4,6}\{2,4,6\} 且特征值为 22 时,XX 的位置在 33
BB 的位置是 {2,4,6}\{2,4,6\} 且特征值为 22 时,XX 的位置在 55

例子 2

假定 k=9,S=7k=9,S=7。那么:
AA 的位置是 {3,4,5,9,10,12,13,16,19}\{3,4,5,9,10,12,13,16,19\} 且特征值为 00 时,XX 的位置在 1414
AA 的位置是 {3,4,5,9,10,12,13,16,19}\{3,4,5,9,10,12,13,16,19\} 且特征值为 77 时,XX 的位置在 1818
BB 的位置是 {3,4,5,9,10,12,13,16,19}\{3,4,5,9,10,12,13,16,19\} 且特征值为 77 时,XX 的位置在 1717

输入格式

只包含一组测试数据。
第一行包含一个整数 kk ,意义如题所述。
第二行包含一个整数 seed\text{seed} ,这个数将用于生成一个 kk 元集合 PP
第三行包含一个整数 SS,意义如题所述。
保证 0Sk107,1seed100000\leq S\leq k \leq 10^7,1\leq \text{seed} \leq 10000
提供了三个用于生成输入数据的文件 cipher.cpp/c/pas。其中读入部分已经完成,在数组 p[]p[] 中,若 p[i]=0p[i] = 0 ,表示 ii 不属于集合 PP,否则,ii 属于集合 PP

输出格式

输出三行,每行一个数,依次对应问题描述中的三个子问题的答案。 即:

  1. 第一个数表示当 kk 元集合 PP 代表 AA 的位置且特征值为 00XX 的位置。
  2. 第二个数表示当 kk 元集合 PP 代表 AA 的位置且特征值为 SSXX 的位置。
  3. 第三个数表示当 kk 元集合 PP 代表 BB 的位置且特征值为 SSXX 的位置。

样例

样例输入 1

5
3344
2

样例输出 1

10
1
2

样例解释 1

第一个样例中,PP 数组为 11 的元素的下标分别为 5,6,7,8,95,6,7,8,9

样例输入 2

500000
4545
234567

样例输出 2

999992
246922
753067

数据范围与提示

对于 30%30\% 的数据,k103k\leq 10^3
对于 50%50\% 的数据,k105k\leq 10^5
对于 100%100\% 的数据,k107k\leq 10^7

对于每个测试点,得分为以下三部分得分之和:

  1. 如果第一问回答正确,你将获得 33 分。
  2. 如果第二问回答正确,你将获得 44 分。
  3. 如果第三问回答正确,你将获得 33 分。

如果你仅仅知道部分答案,请也务必按此格式要求输出三个数,否则你可能会因格式错误无法得分。