3711.陀飞轮
2026-10-25
题解
对于求前缀 s[1…i] 的本质不同的非空子序列,考虑令 x 表示当前所有以 0 结尾的不同非空子序列个数,y 表示所有以 1 结尾的不同非空子序列个数。
那么在末尾添加一个 0,就是将 x←x+y+1,y←y;同理,添加 1 就是 y←x+y+1,x←x。
由于 +1 很不美观,观察发现可以两边同时加 1,令 X=x+1,Y=y+1,那么有 0 时 X←X+Y,Y←Y;1 时 Y←X+Y,X←X。
这样转化以后,每次可以给 X,Y 其中一个加上对方,倒过来看也就相当于辗转相减的过程,也就是说,对于每个串都有一个唯一的满足 gcd(X,Y)=1 的对 (X,Y),反过来也是一样。
具体的将,对于 (X,Y),可以这样得到原串:若 X=Y=1,则原串为空串;若 X>Y,则当前为 0,然后令 X←X−Y;若 X<Y,则当前为 1,然后令 Y←Y−X。
回归到题目,有无解等价于有多少对 X+Y=n+2 且 gcd(X,Y)=gcd(X,n+2)=1(这里 gcd(X,n+2) 是为了引入常量)。
那么比较 φ(n+2) 和 k 大小关系即可。
现在问题来到了如何求字典序第 k 小,根据构造方式,可以猜测 X 越小,字典序越小,证明如下:
证明
考虑归纳证明,对于两个串 (X1,Y1),(X2,Y2),若 Y1X1<Y2X2,则第一个字符串字典序更小。
首先若 ⌊Y1X1⌋=⌊Y2X2⌋,那么可以直接判定。
否则令 t=⌊Y1X1⌋,此时两个串有相同前缀,接下来可以转移到 (X1,Y1−t⋅X1),(X2,Y2−t⋅X2),此时写出新的比值并化简得到:Y1−t⋅X1X1<Y2−t⋅X2X2,完成归纳。
考虑计算 φ(n),直接把 n 质因数分解,复杂度 O(n),然后枚举所有质因子的选择情况进行容斥计算,复杂度 O(2w),直接进行二分 X 判断即可,然后类似于辗转相除法的方式构造原字符串即可。
