[NC记录]AT2363 [AGC012C] Tautonym Puzzle
command_block
2021-04-28 19:53:02
**题意** ： 给定 $n$ ，构造一个字符串 $s$ 满足下列条件 ：
$|s|\leq 200$ ，字符集大小为 $100$。
在 $s$ 的 $2^{|s|}-1$ 个非空子序列中，恰有 $n$ 个是平方串。
（可以证明必定有解）
$n\leq 10^{12}$ ，时限$\texttt{2s}$。
------------
妙啊。
右边构造 `1 2 3 4 ... 100`。
左边也构造一个 $1\sim 100$ 的排列，不难发现左边的一个上升子序列对应一个平方串。
从小到大考虑数。
- 若把该数填在最前面，则方案数 $+1$。
- 若把该数填在最后面，则方案数 $\times 2$。
（此处认为空序列也是上升子序列）
二进制拆分即可。
```cpp
#include<algorithm>
#include<cstdio>
using namespace std;
long long n;
int ans1[105],tn1,ans2[105],tn2;
int main()
{
scanf("%lld",&n);
n++;
for (int i=50,p=-1;i>=0;i--){
if (tn1)ans2[++tn2]=++p;
if (n>>i&1)ans1[++tn1]=++p;
}
printf("%d\n",tn1-1+tn2+100);
for (int i=tn1;i>1;i--)printf("%d ",ans1[i]);
for (int i=1;i<=tn2;i++)printf("%d ",ans2[i]);
for (int i=1;i<=100;i++)printf("%d ",i);
return 0;
}
```