Tautonym Puzzle

Time Limit: 50 Sec Memory Limit: 256 MB

Description

定义一个序列贡献为1，当且仅当这个序列 由两个相同的串拼接而成，比如123123。

请构造一个序列，使得它子序列的贡献和为n。

要求序列长度<=200，权值<=100.

Input

一行一个n。

Output

第一行为长度len，表示你构造出的序列长度。

第二行为你构造出的序列。

Sample Input

7

Sample Output

4
　　1 1 1 1

HINT

n <= 1e12

Solution

构造题到恰好为n的。一般有两种方法：
　　　　1. 可以构造出2^n，并且每部分互不影响；
　　　　2. 有方法添加若干元素使得原有答案*2或+1。

我们先考虑第一种方法。
　　显然我们把 n 化为二进制。并且发现连续 x 个相同的数提供的贡献为2^(x-1)-1，并且若干个连续的不影响。
　　这样 s 需要1+2+……+log2(n)+(log2(n) * 2)（用于补1），极限是900。不能满足条件。

我们再考虑第二种方法。
　　s<=200，权值<=100。长度有5 * log2(n)可用，权值有2 * log2(n)可用。
　　先考虑这样一个问题：
　　　　<p1,p2,…,pk>已经是一个排列了，我们在后面加上**<1,2,…,k>之后的贡献是多少**。
　　显然，此时贡献为：<p1,p2,…,pk>的上升序列的个数。
　　那么我们把问题转化为：构造一个上升序列个数为n的排列。

假设我们原来的排列**<p1,p2,…,pk>已经x个上升序列了，现在填入k+1**。

显然，在前面填一个k+1贡献会变为：x+1。完成了**+1部分。
　　显然，在最后填一个k+1贡献会变为：x*2+1，这里多了一个+1**。怎么办呢？

显然一开始是0，经过3次操作：0*2+1=1，1*2+1=3，3*2+1=7；
　　假设一开始是1，经过3次操作：1*2=2，2*2=4，4*2=8。

发现我们如果将初值1的话，我们每次x*=2，最后再-1和原来的效果是一样的。这样就完成了*2部分。

最后用一个递归即可。

Code

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
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 100005;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

s64 n;
int now;
deque <int> q;

void Solve(s64 n)
{
    if(n == 1) return;
    if(n & 1) Solve(n - 1), q.push_front(++now);
    else Solve(n / 2), q.push_back(++now);
}

int main()
{
    cin >> n;
    Solve(++n);
    printf("%d\n", now << 1);
    while(!q.empty())
        printf("%d ", q.front()), q.pop_front();
    for(int i = 1; i <= now; i++)
        printf("%d ", i);
}