P3770 [CTSC2017] 密钥
题目描述
一个密钥是一个长度为 $n = 2k + 1$ 的字符串，它包含 $1$ 个字母 `X`，$k$ 个字母 `A` 和 $k$ 个字母 `B`。例如 $k = 3$ 时，`BAXABAB` 就是一个密钥。
如下图所示，可以按顺时针顺序把这 $2k+1$ 个字母排成一个圈：
在 $k$ 个字母 `A` 中，有一部分可以定义为 “强的”。具体来说，从 `X` 出发顺时针走到某个 `A` 时，如果途中 `A` 的数目**严格多于** `B` 的数目，则称此字母 `A` 为强的。
对于上面的例子来说，顺时针方向从字母 `X` 数起第 $1$ 个和第 $2$ 个字母 `A` 是强的，而第 $3$ 个字母 `A` 不是强的。
一个密钥的**特征值**就是其中包含的强的字母 `A` 的个数。
天才小朋友 KT 给出了一个结论：
假设 $k$ 个字母 `A` 所在的位置已经固定，但是剩下的 $k$ 个 `B` 和 $1$ 个 `X` 的位置是未知的。（注意，满足这样要求的密钥一共有 $k + 1$ 个，因为字母 `X` 还剩下 $k + 1$ 个可能的位置。）
可以证明：所有这 $k + 1$ 个可能的密钥的特征值是各不相同的，它们恰好为 $0,1,2,\dots,k$。
下面的图是一个具体的示例，从左到右的四个子图中分别有 $3$ 个，$2$ 个，$1$ 个，$0$ 个字母 `A` 是强的。
类似地，如果固定 $k$ 个字母 `B` 的位置，那满足条件的所有 $k + 1$ 个密钥的特征值也各不相同，恰好为 $0,1,2,\dots,k$。
现在你需要解决以下三个问题：
1. 给定密钥中所有 `A` 的位置，当密钥的特征值为 $0$ 时，请问 `X` 在哪个位置。
2. 给定密钥中所有 `A` 的位置，当密钥的特征值为 $S$ 时，请问 `X` 在哪个位置。
3. 给定密钥中所有 `B` 的位置，当密钥的特征值为 $S$ 时，请问 `X` 在哪个位置。
注意：字符串的 $2k + 1$ 个字母的位置由 $1$ 到 $2k + 1$ 编号。
【例子 $1$】
假定 $k = 3,S = 2$。那么：
当 `A` 的位置是 $\{2,4,6\}$ 且特征值为 $0$ 时，`X` 的位置在 $7$；
当 `A` 的位置是 $\{2,4,6\}$ 且特征值为 $2$ 时，`X` 的位置在 $3$；
当 `B` 的位置是 $\{2,4,6\}$ 且特征值为 $2$ 时，`X` 的位置在 $5$。
【例子 $2$】
假定 $k=9,S=7$。那么：
当 `A` 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $0$ 时，`X` 的位置在 $14$；
当 `A` 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $7$ 时，`X` 的位置在 $18$；
当 `B` 的位置是 $\{3,4,5,9,10,12,13,16,19\}$ 且特征值为 $7$ 时，`X` 的位置在 $17$。
输入格式
只包含一组测试数据。
第一行包含一个整数 $k$，意义如题所述。
第二行包含一个整数 $seed$，这个数将用于生成一个 $k$ 元集合 $P$。
第三行包含一个整数 $S$，意义如题所述。
保证 $0 \le S \le k \le 10^7,1 \le seed \le 10000$。
在 `cipher/` 下，包含两个用于生成输入数据的文件 `cipher.cpp/pas`。其中读入部分已经完成，在数组 $p$ 中，若 $p_i=0$，表示 $i$ 不属于集合 $P$，否则，$i$ 属于集合 $P$。
[百度网盘链接>> 密码：9vr3](http://pan.baidu.com/s/1i55NdWx) 请自行编译
```cpp
#include
#include
int p[20000005];
int seed, n, k, S;
int getrand() {
seed = ((seed * 12321) ^ 9999) % 32768;
return seed;
}
void generateData() {
scanf( "%d%d%d", &k, &seed, &S );
int t = 0;
n = k * 2 + 1;
memset(p, 0, sizeof(p));
for( int i = 1; i k ) {
while ( p[i] == 0 ) ++i;
p[i] = 0;
--t;
}
while( t < k ) {
while( p[i] == 1 ) ++i;
p[i] = 1;
++t;
}
}
int main() {
generateData();
return 0;
}
```
输出格式
输出三行，每行一个数，依次对应问题描述中的三个子问题的答案。
即：
1. 第一个数表示当 $k$ 元集合 $P$ 代表 `A` 的位置且特征值为 $0$ 时 `X` 的位置。
2. 第二个数表示当 $k$ 元集合 $P$ 代表 `A` 的位置且特征值为 $S$ 时 `X` 的位置。
3. 第三个数表示当 $k$ 元集合 $P$ 代表 `B` 的位置且特征值为 $S$ 时 `X` 的位置。
说明/提示
【样例解释】
第一个样例中, $P$ 数组为 $1$ 的元素的下标分别为 $5,6,7,8,9$。
【数据范围与约定】
对于 $30\%$ 的数据，$k \le 10^3$。
对于 $50\%$ 的数据，$k \le 10^5$。
对于 $100\%$ 的数据，$k \le 10^7$。
对于每个测试点, 得分为以下三部分得分之和：
1. 如果第一问回答正确，你将获得 $3$ 分。
2. 如果第二问回答正确，你将获得 $4$ 分。
3. 如果第三问回答正确，你将获得 $3$ 分。
**如果你仅仅知道部分答案，请也务必按此格式要求输出三个数。否则你可能会因格式错误无法得分。**