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

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

题目链接（正睿）

题目大意

定义\(s_n=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\)，满足\(|s_n|>m+1\)，答案就是\(m-|s_{n-2}|\)。下面给出证明：

首先，可以将\(s_n\)进行如下变换： \[ \begin{aligned} s_n & =s_{n-1}+s_{n-2}\\ & =s_{n-2}+s_{n-3}+s_{n-2}\\ & =s_{n-2}+s_{n-3}+s_{n-3}+s_{n-4}\\ & =s_{n-2}+s_{n-3}+s_{n-4}+s_{n-5}+s_{n-4}\\ & =s_{n-2}+s_{n-2}+s_{n-5}+s_{n+4} \end{aligned} \] 此时，如果\(m=|s_{n-2}|\times 2\)，答案就是\(s_{n-2}\)。那么根据结论，如果让\(m+1\)，最大匹配长度也会\(+1\)，如何证明呢？

我们考虑将\(s_{n-2}\)变形： \[ \begin{aligned} s_{n-2} & =s_{n-3}+s_{n-4}\\ & = s_{n-4}+s_{n-5}+s_{n-4}\\ & = s_{n-5}+s_{n-6}+s_{n-5}+s_{n-4} \end{aligned} \] 那么， \[ \begin{aligned} s_n&=s_{n-5}+s_{n-6}+s_{n-5}+s_{n-4}\\ & +s_{n-5}+s_{n-6}+s_{n-5}+s_{n-4}\\ & +s_{n-5}+s_{n-4} \end{aligned} \] 可以发现，第一行起五个字符串和第二行起五个字符串是匹配的（即\(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;
}