[AGC012C] Tautonym Puzzle
本题考查增量构造。具体而言如下递归构造 \(f(n)\)（假设它需要的递归已经构造好）：
- 当 \(n\) 为奇数时，可以先构造 \(f((n-1)\div2)\)，然后在中部和尾部添加一个新的数。由于新的数可以接在原来任意一个子序列后，所以 \(\times 2\)，\(+1\) 是因为两个新数自己组成一个序列。
- 否则，构造 \(f(n-1)\)，然后在头部和尾部添加一个新的数，此时只有两个新数组成新的序列。
- 当 \(n=0\) 时，返回。
#include<cstdio>
#include<queue>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
typedef long long ll;
ll n;
int idx;
deque<int>q1,q2;
void dfs(){
if(!n)return;
if(n&1){
n>>=1;
dfs();
q1.push_back(++idx);
q2.push_back(idx);
}
else{
n--;
dfs();
q1.push_front(++idx);
q2.push_back(idx);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#endif
// Insert Code Here
scanf("%lld",&n);
dfs();
printf("%d\n",q1.size()+q2.size());
for(int v:q1)printf("%d ",v);
for(int v:q2)printf("%d ",v);
return 0;
}