神秘脑电波还在追我？？？

题意

给定 $n$，要求构造长度不超过 $1000$、字符集不超过 $62$ 的字符串使其本质不同子序列个数恰好 $=n$。

思路

首先需要意识到，几个特殊性质是用来帮助你骗分不是用来帮助你过题的。

然后需要意识到，这个限制及其宽松。所以我们考虑加强：将字符集缩到 $\{0,1\}$！

这样我们的思路就集中多了。尝试对一个字符串进行计数。

设 $dp_{i,{0/1}}$ 表示前 $i$ 项中以 $0/1$ 结尾的子序列个数。对于一个长为 $l$ 的字符集为 $\{0,1\}$ 的序列 $a$ 则有转移：

$$$ dp_{i,a_i}=dp_{i-1,0}+dp_{i-1,1}\\ dp_{i,\neg a_i}=dp_{i-1,\neg a_i} $$$

初始 $dp_{0,0}=dp_{0,1}=1$，最终答案为 $dp_{l,0}+dp_{l,1}-1$。

又假如现在我们已经有了 $dp_{l,0}+dp_{l,1}=n+1$，考虑验证其是否是合法的。

我们先不用管 $l$ 的限制。若要从 $dp_{i,0/1}$ 推回 $dp_{i-1,0/1}$ 的话必然是将大的减去小的，且如果合法的话，减到最后会剩下 $1,1$，再进行一次就是 $1,0$。

这玩意不是辗转相减吗？所以这个等价于 $\gcd(dp_{l,0},dp_{l,1})=1$！我们只需找到一组 $dp_{l,0/1}$ 满足它们互质即可。

这玩意等价于 $dp_{l,0}$ 与 $n+1$ 互质，也就是说，如果我们随机一个，合法的概率为 $\dfrac{\varphi(n+1)}{n+1}$。根据一些神秘计算我们得知这玩意的期望值为 $\dfrac{6}{\pi^2}\approx0.6079$，于是期望取 $1.645$ 次就能找到合法的。

但是我们刚刚没有考虑 $l\le 1000$ 的限制！辗转相除的期望次数是 $\log n$，但是我们在做辗转相减！

考虑什么情况下会爆炸，也就是当 $dp_{i,j}$ 远大于 $dp_{i,\neg j}$ 时会减一亿次。那我们能做的只有将 $dp_{l,0}$ 的初值设的范围小一点，差不多在 $[0.4\times n,0.6\times n]$ 这样。不过不管这个好像也能过就是了。

时间复杂度 $O(能过\times T\times l)$。

代码

友情提示：不要用 rand()。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, T, len;
char ans[1002];
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}
mt19937_64 rnd(random_device{}());
inline ll rd(ll l, ll r) {
    return rnd() % (r - l + 1) + l;
}
int main() {
	cin >> T;
	while (T -- ) {
		cin >> n; n ++;
		while (1) {
			len = 0;
			ll dp0 = rd(1, n - 1), dp1 = n - dp0;
			while (gcd(dp0, dp1) != 1) dp0 = rd(1, n - 1), dp1 = n - dp0;
			while (len <= 1000 && (dp0 > 1 || dp1 > 1)) {
				if (dp0 > dp1) dp0 -= dp1, ans[++ len] = 's';
				else dp1 -= dp0, ans[++ len] = 'b';
			}
			if (dp0 > 1 || dp1 > 1) continue;
			for (ll i = 1; i <= len; i ++ ) putchar(ans[i]);
			putchar('\n');
			break;
		}
	}
}