#P3558. [Ctsc2014]小秘密

    ID: 2677 传统题 4000ms 256MiB 尝试: 14 已通过: 5 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS位运算异或抵消多项式与生成函数FWTCF3000

[Ctsc2014]小秘密

[CTSC2014] 小秘密

题目描述

阿米巴把他与小强的掷币结果记录成一个二进制串,11 表示正面,00 表示反面。他使用带参数 NN、密钥 K1,K2K_1,K_2 和寄存器 XX 的算法加密记录。两个密钥都是不超过 2N2^N 的 6464 位二进制数。

先令 X0=K1X_0=K_1。按顺序读入明文的每一位 IpI_p,计算并输出密文位 OpO_p,然后继续处理下一位。

$$\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}$$

and⁡\operatorname{and} 为按位与,xor⁡\operatorname{xor} 为按位异或。w(x)w(x) 是 xx 的二进制表示中 11 的个数对 22 取模的结果。例如 w(13)=w((1101)2)=1w(13)=w((1101)_2)=1,w(12)=w((1100)2)=0w(12)=w((1100)_2)=0。

后来阿米巴忘记了密钥。小强告诉他,这枚硬币落到反面的概率为 12+b\tfrac12+b。给定一整份密文,请恢复 K2K_2。

输入格式

标准输入是一段长度为 10485761048576 字节的原始二进制数据,包含 83886088388608 个密文位。每字节按从最高位到最低位的顺序读。例如比特串 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 示例用于本地读取样例文件。正式评测仍从标准输入读取全部 10485761048576 字节。

输出格式

输出一行恰有 6464 个字符的二进制串,表示 K2K_2。从最高位到最低位排列,不足 6464 位时在开头补 00。

原赛样例

原赛提供随机样例生成器。本题附件提供按原赛加密规则重写的 cryptogen.py。在该文件所在目录运行以下命令,其中 N,bN,b 为生成参数。

python cryptogen.py 50 0.3

生成器输出 crypto.in 和 crypto.ans,并把明文和辅助信息保存到 crypto.log。同样的参数可能生成不同文件,应保留每次生成的样例。

数据范围

原赛测试点 NN bb
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

提示

四个相互独立、各以 0.620.62 的概率发生的事件中,恰有奇数个发生的概率约为 0.498341120.49834112。要高置信地区分正面概率为 12\tfrac12 或 12−d\tfrac12-d 的硬币,所需的抛掷次数与 d−2d^{-2} 同阶。