#P11683. [2021年联测]造

    ID: 10834 传统题 3000ms 512MiB 尝试: 4 已通过: 1 难度: 8 上传者: 标签>动态规划组合数学CF2400构造枚举数学分治

[2021年联测]造

3 造

3s | make.cpp | 512MB

3.1 Statement

小 S 喜欢上升子序列。

给定整数KK,构造一个整数序列满足其上升子序列种数为KK,你的得分与序列长度相关。注意如果某个上升子序列出现了多次,应只计数一次,空序列算作一个上升子序列。

3.2 Input Format

多组测试数据,第一行一个整数TT表示测试数据组数,接下来TT行每行一个整数KK。

3.3 Output Format

对于每组测试数据输出两行,第一行一个整数LL 表示序列长度,第二行LL 个整数表示输出序列。你需要保证输出的L≤128L\le 128,序列中的数在 [0,999][0,999] 范围内。

3.4 Sample 1

见 make1.in 和 make1.out。

3.5 Sample 1 Explanation

注意样例输出仅为一组合法输出。下面对于样例输出给出解释。

对于第 1 组数据,上升子序列有 ()(1)(4)(5)(1,4)(4,5)(1,5)(1,4,5) 这 8 个,注意 (1) 在序列中出现了多次,但是应该只计入一次。

对于第 2 组数据,上升子序列有 ()(0)(1)(8)(9)(1,8)(1,9) 这 7 个。

对于第 3 组数据,上升子序列有 ()(0)(1)(4)(9)(0,1)(1,4)(1,9)(4,9)(1,4,9) 这 10 个。

3.6 Constraints & Hints

本题共有两个测试点。测试点 11 满足T=1500,1≤K≤1500T=1500,1\le K\le 1500,计 10 分;测试点 22 满足T=1500,1≤K≤5×1018T=1500,1\le K\le 5\times 10^{18},计 90 分。

本题有部分分:对于每组数据,输出合法的前提下,按照如下表格你可以获得对应百分比的分数。一个测试点的分数为其下所有测试数据的分数的最小值。

L∈L\in [129,+∞)[129,+\infty ) [120,128][120,128] [112,119][112,119] [104,111][104,111] [99,103][99,103] [0,98][0,98]
分数 0 20%20\% 40%40\% 60%60\% 80%80\% 100100%