#L6566. 月之都的密码

月之都的密码

题目描述
*题目描述可能与東方Project東方Project原设定不完全相符。

月之都月之都正在阴谋向幻想乡幻想乡迁移!

奇怪的机械已经在幻想乡幻想乡中移动,并在「净化」幻想乡幻想乡——他们在试图让幻想乡幻想乡不再存在生物!灵梦灵梦不得不再次与早苗早苗魔理沙魔理沙一同前去解决异变。

很快,她们便解决掉了在幻想乡幻想乡前线的月兔清兰月兔清兰铃瑚铃瑚,并成功拿到了几台向月都月都发送情报时的加密工具。但是由于魔理沙魔理沙一个魔炮轰上去把铃瑚铃瑚BB带走了,所以这些加密工具也接近报废了。

经过河城荷取河城荷取对窃听到的密文情报以及这台加密仪器的分析,她发现月都月都在前线发回的情报的加密方式其实比较简单。大约可以描述如下:

月都月都发来的情报的字符集大小为nn,则加密过程是将[1,n][1,n]中的nn个整数一一对应到[1,n][1,n]的整数上。或者说,这个过程f(x)f(x)是一个[1,n][1,n][1,n][1,n]的双射。
而这些加密仪器,则可以在一次使用中对于任意给定的集合SS,给出加密后的集合S={xx=f(a),aS}S'=\{x \mid x=f(a), a \in S\}
但是根据河城荷取河城荷取的分析,一台仪器最多再使用TT次就会彻底报废。每台仪器所保有的加密方式以及TTnn根据损坏情况与用途各不相同。

为了获取更多的计划情报,她们需要利用这些接近报废的加密仪器解出它们密文到原文的映射f(x)f'(x)
由于这些仪器已经接近报废,她们需要尽快找到方法来解出解密所有月都月都情报的方法。
于是八云紫八云紫随手拉开一道隙间把你拉了出来,要你解决这个问题。如果不行就把你拉去隙间掉!

为了保命,你需要写一个程序完成所有几台仪器的处理。你的程序需要一次处理一台。

交互方式
你有两种交互方式:第一种是使用标准输入输出交互(CodeforcesCodeforces风格),第二种是使用函数调用来进行交互(WC/APIO/IOIWC/APIO/IOI风格)。

注意,我们提供的第二种交互方式的接口的底层实现是对第一种交互的简易封装。但是建议使用第二种来避免可能出现的InvalidInteractionInvalid Interaction错误。

标准I/OI/O交互
首先你的程序可以从标准输入读取两个整数nnTT,含义如题目描述所述。

你可以通过标准输出执行两种命令:

  • encodeencode命令:用于进行一次加密操作。其后应跟随一个数字kk表示加密集合的大小,后跟kk个空格分隔的整数表示你要加密的集合。
    例:encode3514495233encode 3 514 495 233表示对集合{233,495,514}\{233,495,514\}进行加密。
    该命令执行完毕后,你的程序可以在标准输入流中读取kk个数,表示加密结果。
    注意:你要尝试加密的集合不能带重。

  • submitsubmit命令:表示你已经得到了答案。其后应该有nn个空格分隔的整数,第ii个数表示ii解密后的值。
    你的程序在输出此命令后应当立即结束。
    例:若n=3n=3,你找到的解密方案是121 \rightarrow 2232 \rightarrow 3313 \rightarrow 1,则你应当执行:submit231submit 2 3 1

注意:如果你使用标准I/OI/O进行交互,需要在输出命令后刷新stdoutstdout缓冲区(如std::flushstd::flushstd::endlstd::endlfflush(stdout)fflush(stdout))。

函数调用交互
此部分仅支持C++C++语言。

首先需要包含头文件interaction.hinteraction.h

你需要实现如下函数:
std::vector<int>Decode(intn,intT)std::vector<int> Decode(int n, int T)

在每个测试点中,交互库会调用该函数恰好一次。
参数intnint n为题目描述中的nnintTint T为题目描述中的TT
函数返回值为包含密码表的std::vector<int>std::vector<int>,其中下标为ii的位置的值是i+1i+1的解密结果。

交互库中可调用的函数:
std::vector<int> Encode(const std::vector<int>& v)
该函数返回vv中值的加密结果。注意:加密集合不能带重。

数据范围与提示
本题共有2020个测试点,各测试点的nn(字符集大小)和TT(最大查询次数)如下表:

测试点编号 nn TT 测试点编号 nn TT
11 00 1111 10001000 300300
22 100100 9999999999 1212 100000100000 1000010000
33 10001000 (未明确) 1313 2020 66
44 100000100000 1414 100100 1515
55 2020 1515 10001000 4040
66 100100 7575 1616 100000100000 10201020
77 10001000 500500 1717 2020 55
88 100000100000 5000050000 1818 100100 77
99 2020 77 1919 10001000 1010
1010 100100 3535 2020 100000100000 1717
  • 若程序未提交正确答案并正常结束,该测试点得00分。
  • 若程序提交正确答案,但encodeencode命令调用次数超过TT,该测试点得00分;否则得满分。
  • 注意:交互底层为标准I/OI/O管道,总通信量过大可能导致超时。建议查询的S\sum |S|不超过1×1071 \times 10^7级别。