【题解】对你的爱深不见底

发表于 分类于 阅读次数： Valine：

题目链接（正睿）

题目大意

定义$sn=s{n-1}+s_{n-2}$定义字符串的权值为最大的$i<|s|$满足$s$的长度为$i$的前缀等于长度为$i$的后缀。给定$n,m$，求字符串$s_n$的前$m$个字符的权值。

$n\le 10^3$

分析

首先很容易就想到，权值的定义就是$\text{KMP}$中$border$数组的定义，所以递推出$s_n$后跑$\text{KMP}$即可，可以拿到$30$分。

之后将答案打表，可以发现如下规律：

找到最小的$n$，满足$|sn|>m+1$，答案就是$m-|s{n-2}|$。下面给出证明：

首先，可以将$s_n$进行如下变换：

此时，如果$m=|s{n-2}|\times 2$，答案就是$s{n-2}$。那么根据结论，如果让$m+1$，最大匹配长度也会$+1$，如何证明呢？

我们考虑将$s_{n-2}$变形：

那么，

可以发现，第一行起五个字符串和第二行起五个字符串是匹配的（即$s{n-5}+s{n-6}+s{n-5}+s{n-4}+s{n-5}$），只有最后一个$s{n-4}$不匹配。我们将$s{n-4}$像上面一样继续拆分成$s{n-6}+s{n-7}+s{n-6}$，这样就可以继续和第二行的$s_{n-6}$匹配。以此类推，最后只剩下两个字符不能匹配，$m$是不可能包含这两个字符的，因为$m+1<|s_n| \to m<|s_n|-1 \to m \le |s_n|-2$。

注意需要使用高精度。

实现

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main() {
    cin >> t;
    while (t--) {
        n = read();
        m = read();
        ll len = 0, sa = 1, sb = 1, lst = 0;
        while (len <= m + 1) {
            len = sa + sb;
            lst = sb;
            sb = sa;
            sa = len;
        }
        int ans = (m - lst) % mod;
        printf("%d\n", ans);
    }
    return 0;
}