AT2363-[AGC012C]Tautonym Puzzle【构造】

正题

题目链接:https://www.luogu.com.cn/problem/AT2363

---

题目大意

给出(n)，要求构造一个字符串(s)，使得能够找出恰好(n)个子序列使得这个子序列能划分成前后相等的两份。
要求(|s|leq 200)，字符集为([1,100])

(1leq nleq 10^{12})

---

解题思路

很妙的想法，我们把(s)分成两半，一半是(1sim x)，然后后一半是一个(1sim x)的排列，这样答案就是这个排列的上升子序列数。

这样就化成了一个很简单的构造了，从小到大加，加到前面就是(+1)，后面就是( imes 2)。

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
ll n,cnt,flag;deque<ll> q;
signed main()
{
	scanf("%lld",&n);n++;
	for(ll i=63;i>=0;i--){
		if(flag){
			cnt++;
			q.push_back(cnt);
		}
		if((n>>i)&1){
			if(flag)cnt++,q.push_front(cnt);
			flag=1;
		}
	}
	printf("%lld
",cnt*2);
	for(ll i=1;i<=cnt;i++)
		printf("%lld ",i);
	for(ll i=1;i<=cnt;i++)
		printf("%lld ",q.front()),q.pop_front();
	return 0;
}