题解：P12775 [POI 2018/2019 R1] 子序列 Subsequences

· · 题解

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

题意

给定 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;
        }
    }
}