#P3558. [Ctsc2014]小秘密
[Ctsc2014]小秘密
[CTSC2014] 小秘密
题目描述
阿米巴把他与小强的掷币结果记录成一个二进制串, 表示正面, 表示反面。他使用带参数 、密钥 和寄存器 的算法加密记录。两个密钥都是不超过 的 位二进制数。
先令 。按顺序读入明文的每一位 ,计算并输出密文位 ,然后继续处理下一位。
$$\begin{aligned} T_p&=w\bigl(f(X_p)\operatorname{and}K_2\bigr),\\ O_p&=I_p\operatorname{xor}T_p,\\ X_{p+1}&=(2X_p+O_p)\bmod 2^N,\\ f(x)&=(1994x^5+11x^4+4x^3+1995x^2+9x+24)\bmod 2^N. \end{aligned}$$为按位与, 为按位异或。 是 的二进制表示中 的个数对 取模的结果。例如 ,。
后来阿米巴忘记了密钥。小强告诉他,这枚硬币落到反面的概率为 。给定一整份密文,请恢复 。
输入格式
标准输入是一段长度为 字节的原始二进制数据,包含 个密文位。每字节按从最高位到最低位的顺序读。例如比特串 011000010110110101100010 记录为 amb 三个字节。
可以用 fread 逐字节读取标准输入。在会转换文本换行的平台上,应将标准输入设为二进制模式。
#include <stdio.h>
#ifdef _WIN32
#include <fcntl.h>
#include <io.h>
#endif
int main(void) {
static unsigned char data[1 << 20];
#ifdef _WIN32
_setmode(_fileno(stdin), _O_BINARY);
#endif
size_t bytes = fread(data, 1, sizeof data, stdin);
return bytes == sizeof data ? 0 : 1;
}
原题也提供 Pascal 的 BlockRead 示例。以下保留原来的二进制文件读取写法,并令缓冲区长度与实际密文长度一致。
program crypto;
var
MyFile: file;
Data: array [0..1048575] of Byte;
begin
Assign(MyFile, 'crypto.in');
Reset(MyFile, 1);
BlockRead(MyFile, Data, SizeOf(Data));
Close(MyFile);
end.
上面的 Pascal 示例用于本地读取样例文件。正式评测仍从标准输入读取全部 字节。
输出格式
输出一行恰有 个字符的二进制串,表示 。从最高位到最低位排列,不足 位时在开头补 。
原赛样例
原赛提供随机样例生成器。本题附件提供按原赛加密规则重写的 cryptogen.py。在该文件所在目录运行以下命令,其中 为生成参数。
python cryptogen.py 50 0.3
生成器输出 crypto.in 和 crypto.ans,并把明文和辅助信息保存到 crypto.log。同样的参数可能生成不同文件,应保留每次生成的样例。
数据范围
| 原赛测试点 | ||
|---|---|---|
| 1 | 5 | 0.12 |
| 2 | 20 | |
| 3 | 50 | 0.5 |
| 4 | 0.4 | |
| 5 | 0.35 | |
| 6 | 0.3 | |
| 7 | 60 | 0.2 |
| 8 | 0.15 | |
| 9 | 0.13 | |
| 10 | 0.12 |
提示
四个相互独立、各以 的概率发生的事件中,恰有奇数个发生的概率约为 。要高置信地区分正面概率为 或 的硬币,所需的抛掷次数与 同阶。