题目链接：https://qoj.ac/problem/6351

题目大意：问你内恰有 $n$ 个本质不同子序列的且字典序排名为 $k$ 的 $01$ 串是啥。

做法

非常 amazing 的一道题目。

首先想想对于一个 $01$ 串怎么求本质不同的 $01$ 串个数，因为我记得之前队友做过一道这样的题目，做法是万能欧几里得。

设 $f_0$ 表示添加 $0$ 后变成新的子序列的串，$f_1$ 同理。

初始时 $f_0=f_1=1$ ，可以发现，转移就是：

$f_0=f_0+f_1$ （添加 $1$）

$f_1=f_0+f_1$ （添加 $0$）

而子序列个数恰好等于 $f_0+f_1-2$ 。

可以发现，这个过程是 gcd 的逆过程（把取模的过程看成一个个减的过程），因此顺过来看，$f_0$ 必须满足和 $n+2$ 互质，即任意一个本质不同字串个数等于 $n+2$ 的串对应一个与 $n+2$ 互素的数字，而 $01$ 串其实就是其 gcd 的过程。（因此无解就是 $>\phi(n+2)$）

因此现在就是要找过程字典序第 $k$ 小的与 $n+2$ 互素的 $x$ 。

这怎么找呢？设数字为 $(x,y=n-x)$ （为了方便，后面都认为 $n=n+2$ ），不妨考虑逆着求本质不同子序列个数，这样来做一一对应，其过程就等价于这样的字符串：

从左到右，出现 $0$ 就 ：$y-x$ ，出现 $1$ 就 $x-y$ ，做完后 $x=y=1$ 。

注：这同时也证明了，对于一个 $01$ 串，拿着 $(1,1)$ 正着跑和倒着跑最后得到的 $x+y$ 的值是一样的。同时，在后面会频繁出现拿着 $(x,y)$ 跑一遍字符串这种话，一般情况下，如果 $x,y\le 1$ ，做的是加法的那种跑，否则是减法的那种跑。

这样就可以二分了，由于我们知道 $gcd$ 的过程中，$01$ 转化不会超过 $O(\log)$ 次，所以总时间复杂度为 $O(\log^2)$ 的。

由于具体过程中并不知道二分的上界，我选择倍增。

倍增是这样子倍增：$x’=ax-bn,y’=-cx+dn$ ，其中要求 $x’\ge 0, y’ \ge 0,x\ge 1$ ，从而得到初值 $x$ 的上界和下界，然后上界等于下界时，得到最终答案 $x$ 。

当我们想要确定 $0$ 的数量时，我们就设 $y’’=y’-kx’$ ，可以发现如果 $(x’,y’)$ 对应的区间为 $[l,r]$ ，那么 $(x’,y’’)$ 对应的区间为 $[l,r’]$ ，只要确保其中的数字够 $k$ 就行了。

$1$ 的数量类似，不过我们需要先计算出其是这个区间中字典序排名第几大的，相当于取个反。

感觉还是蛮有细节需要证明的，有些东西不会证明就直接判掉了。

细节 1 ：$\exist x\in[l,r]:gcd(x,n)=1,$ 且 $(x,n-x)$ 进行当前跑出来的 $01$ 串能够变成 $(1,0)/(0,1)/(1,1)$ 的必要条件是 $l=r$ 或者 $l=n-1,r=n$ 。

证明

$(1,1)$ ：

$ax-bn\ge0, -cx+dn\ge0$ 在取到特解 $x’$ 时满足：$ax-bn=1, -cx+dn=1$ 。

可以发现，上界 $\ge x’$ 。

$-c(x’+1)+dn=1-c$ ，当 $c>1$ 时上界 $=x’$ ，否则此时 $c=1$，意味着 $d=1$ ，所以上界为 $n$ ，$x’=n-1$ ，又 $n\ge 3$ ，所以至少有一个 $1$ ，由下面的讨论知道 $l=n-1,r=n$ 。

$a(x’-1)-bn=1-a$ ，当 $a>1$ 时下界 $>x’-1$ 。

$a=1$ 意味着 $b=0$ ，所以过程是 $00000…$ ，这个时候可以发现下界为 $0$ ，故 $x’=1$ ，但又有额外要求：$x\ge 1$ ，所以此时区间中只有一个数字。

剩下的两个状态一定会经过 $(1,1)$ ，证毕。

细节 2 ：过程中的 $a,b,c,d$ 会不会爆 long long （一旦区间中只有一个数字就退出）。

证明

不难发现，我们可以将倍增过程中的减号全部变成加号，状态改成 $(ax+bn,cx+dn)$ ，不会影响 $a,b,c,d$ ，这样我们只要拿着 $(1,1)/(1,0)$ 倒着跑一遍就可以得到 $a,b,c,d$ 的精确值。

首先倍增过程中一致保持着 $[l,r]$ 中是有合法解的，因此区间中一旦只有两个数字，分为两种情况讨论：

  1. 此时这个唯一的合法解超过 $(1,1)$ ，即恰好或者还没到，因此绝对 $\ge (1,1)$ 。注 ：我们认为 $(a,b)\ge(c,d)$ 等价于 $a\ge c,b\ge d$ ，直接拿着 $(1,1)$ 倒着跑，就可以得到范围 $\le n$ ，不会爆。

  2. $(0,1)/(1,0)$ ，以 $(1,0)$ 举例，初始区间为 $[1,n]$ ，因此过程是非空的，又由于是区间长度一为 $1$ 我们就退出，我们先假设上一步中的区间不是 $[n-1,n]$ ，那么过程最后一个字符一定为 $0$ ，扔掉这个字符后的结果为 $(1,1)$ ，因此我们从左边拿着 $(1,1)$ 走完这个字符串得到的结果 $\le 2n$ 。

    如果是 $[n-1,n]$，那么 $a=n,b=n-1,c=1,d=1$ ，在倍增一次后变成：$a=n,b=n-1,c=n+1,d=n$ ，直接退出，因此，范围还是在 $O(n)$ 的。

综上，范围是在 $O(n)$ 的，不会爆 long long 。

其余小的细节就不再赘述了。

最终时间复杂度：$O(T\sqrt{n}\log^2n)$ 。（还要算区间中与 $n$ 互素的数字个数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
PLL operator+(PLL x, PLL y){return {x.first + y.first, x.second + y.second};}
PLL operator-(PLL x, PLL y){return {x.first - y.first, x.second - y.second};}
PLL operator*(PLL x, LL y){return {x.first * y, x.second * y};}
PLL operator*(LL x, PLL y){return y * x;}
//x.first * t + y.second * n
LL n, K;
PLL getrange(PLL l, PLL r){return {max((l.first - 1 - l.second * n) / l.first, 1ll), - r.second * n / r.first};}
void printans(LL x){
    vector<PLL> ans;
    LL y = n - x;
    while(x > 1 || y > 1){
        assert(x && y);
        if(x > y){
            ans.push_back({1ll, x / y});
            x %= y;
        }
        else{
            ans.push_back({0ll, y / x});
            y %= x;
        }
    }
    ans.back().second--;
    cout << ans.size() << " " << (*ans.begin()).first << "\n";
    for(auto [d, cnt] : ans) cout << cnt << " ";
    cout << "\n";
}
vector<LL> p;
vector<LL> fac;
LL query(LL x){
    LL ans = 0;
    for(int i = 0; i < fac.size(); i++){
        if(__builtin_popcount(i) & 1) ans -= x / fac[i];
        else ans += x / fac[i];
    }
    return ans;
}
LL query(LL l, LL r){return query(r) - query(l - 1);}
void solve(){
    p.clear();
    fac.clear();
    cin >> n >> K;
    n += 2;
    {
        LL now = n;
        for(LL i = 2; i * i <= now; i++){
            if(now % i != 0) continue;
            p.push_back(i);
            while(now % i == 0) now /= i;
        }
        if(now > 1ll) p.push_back(now);
        fac.push_back(1ll);
        for(auto x : p){
            int pre = fac.size();
            for(int i = 0; i < pre; i++) fac.push_back(fac[i] * x);
        }
    }
    if(query(1, n) < K){
        cout << "-1\n";
        return ;
    }
    PLL left, right;
    left = {1ll, 0ll};
    right = {-1ll, 1ll};
    int type = 0;
    while(1){
        auto [l1, r1] = getrange(left, right);
        if(l1 == r1) break;
        if(!type){//determine 0 cnt
            LL k;
            for(LL k = 1ll;;k *= 2){
                PLL nex = right - left * k;
                auto [l2, r2] = getrange(left, nex);
                if(l2 > r2 || query(l1, r2) < K) break;
                right = nex;
                if(l2 == r2) break;
            }
            for(; k; k /= 2){
                PLL nex = right - left * k;
                auto [l2, r2] = getrange(left, nex);
                if(l2 > r2 || query(l1, r2) < K) continue;
                right = nex;
                if(l2 == r2) break;
            }
        }
        else{
            LL k;
            for(k = 1ll;;k *= 2){
                PLL nex = left - right * k;
                auto [l2, r2] = getrange(nex, right);
                if(l2 > r2 || query(l2, r1) < K) break;
                left = nex;
                if(l2 == r2) break;
            }
            for(; k; k /= 2){
                PLL nex = left - right * k;
                auto [l2, r2] = getrange(nex, right);
                if(l2 > r2 || query(l2, r1) < K) continue;
                left = nex;
                if(l2 == r2) break;
            }
        }
        auto [l2, r2] = getrange(left, right);
        K = query(l2, r2) - K + 1;
        type ^= 1;
    }
    printans(getrange(left, right).first);
}
int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

感觉我的做法有点麻烦了，看看正解。

官方做法

在除了实现以外的部分基本一样，但最后还是唐了，终究逃不出唐的魔爪。

注意到一个事情，我们在二分 $0$ 的个数的时候，上界向下，这启示我们 $x$ 越小字典序越小。

$1$ 的个数的时候，下界网上，这启示我们 $x$ 越大字典序越大。

这两件事综合起来就可以证明：$x$ 的大小等价于字典序的大小。

事实上，也可以直接去证明，对于 $(x_1,y_1)/(x_2,y_2)\to (1,1)$ 的过程，如果 $x_1y_2$ ，可以用归纳法加一些小讨论证明前者的过程要 $<$ 后者的过程。（注意：$gcd(x_1,y_1)=1,gcd(x_2,y_2)=1$ ）

然后直接二分就行了。

完了，感觉自己唐完了。我记得我有过这个想法，但是在发现二分 $1$ 的时候 $1$ 下界是往上走时就觉得错完了，但是忘记下界往上走对应 $1$ 的个数更多，对应字典序越大，实际上是对完了，结果就是我唐完了。

真是艹了，这样确实好写多了，不过我也懒得再写一遍了。

时间复杂度 ：$O(T\sqrt{n}\log{n})$ 。