题目大意：

T≤1000T\le 1000组数据，每组数据给定m≤109m\le 10^9，要求构造长度小于100100的一个排列，使得排列中最长上升子序列的数量为mm

如果不存在这样的排列，输出−1-1，否则输出这个排列

思路：

思路1

比赛的时候第一反应是直接输出从mm到11，超过100100的情况不存在答案。但是很快意识到构造LIS数量为mm的排列的长度完全没必要到mm

队友：m=27，构造3 2 1 6 5 4 9 8 7满足答案

思路2

队友顺着这个思路提出的。把mm质因数分解，设m=∏pikim=\prod p_i^{k_i}，把排列构造成∑ki\sum k_i段的形式，每段的长度为pip_i，设当前已经使用的数的区间为[1,d][1,d]，每段内的形式为d+pi,d+pi−1,…,d+1d+p_i,d+p_i-1,\dots,d+1

例如m=60=223151m=60=2^23^15^1，构造排列2 1 4 3 7 6 5 12 11 10 9 8

当100100以内的质数无法将mm分解，或∑piki>100\sum p_ik_i>100时无解

然而这个思路依然是错的

场上比较成熟的思路（至少对我而言）基本上就到这里了，队友找了一些规律发现了一些与三进制有关的性质

思路3（正解）

官方题解没太看明白，直接贴在这里吧

solution

以下是我根据队友补题代码得到的自己的理解，应该跟官方题解是等价的

记m−1m-1的二进制表示为bkbk−1…b0b_{k}b_{k-1}\dots b_0，其中bk=1b_k=1

考虑首先构造排列4,3,7,6,…,3k+1,3k,1,2,5,…,3k−14,3,7,6,\dots,3k+1,3k,1,2,5,\dots,3k-1

也就是分成三段，第一段每个单元形如3i+1,3i3i+1,3i，第二部分为11，第三部分每个单元形如3i−13i-1

此时第二部分与第三部分构成了序列中唯一的LIS，长度为k+1k+1，而第一部分内的数构成了2k2^k个长度为kk的上升子序列

考虑bi−1b_{i-1}，若bi−1=1b_{i-1}=1，则将3i−13i-1与3i3i交换。

考虑一次交换的影响。交换后，第一部分和第三部分中各项之间的大小关系没有发上改变，故第一部分仍仅构成了2k2^k个长度为kk的上升子序列，第三部分仍为长度为k+1k+1的上升子序列。但交换后的3i−13i-1与3i3i，使得在第一部分中，由前i−1i-1个单元的上升子序列，可以经由3i−13i-1再到3i3i在接到第三部分的一段后缀，所得到的上升子序列长度为(i−1)+1+(k−i+1)=k+1(i-1)+1+(k-i+1)=k+1，恰为LIS的长度，新增的这样的LIS一共有2i−1个2^{i-1}个。

这样，我们通过一次交换可以让LIS的数量增加2i−12^{i-1}个，从而我们可以以3[log⁡2m]+13[\log_2m]+1的长度构造出符合条件的排列。

代码

由于题目不要求长度最短，所以m−1m-1中出现前导00也没有关系。题目所给数据范围为m≤109m\le 10^9，其二进制位最多有3030为，故直接构造长度为9191的排列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int m;
int p[100];

void Work()
{
    read(m);
    memset(p,0,sizeof(p));
    --m;
    p[60]=1;
    int cur=1;
    for(int i=0;i<30;i++)
    {
        if(m>>i&1)
        {
            p[2*i+1]=++cur;
            p[61+i]=++cur;
            p[2*i]=++cur;
        }
        else
        {
            p[61+i]=++cur;
            p[2*i+1]=++cur;
            p[2*i]=++cur;
        }
    }
    puts("91");
    for(int i=0;i<91;i++)
    {
        printf("%d ",p[i]);
    }
    puts("");
}