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

发表于 分类于 阅读次数： Valine： 本文字数： 554 阅读时长 ≈ 2 分钟

题目链接（正睿）

题目大意

定义定义字符串的权值为最大的满足的长度为的前缀等于长度为的后缀。给定，求字符串的前个字符的权值。

$n\le 10^3$

分析

首先很容易就想到，权值的定义就是中数组的定义，所以递推出后跑即可，可以拿到分。

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

找到最小的，满足，答案就是。下面给出证明：

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

此时，如果，答案就是。那么根据结论，如果让，最大匹配长度也会，如何证明呢？

我们考虑将变形：

那么，

可以发现，第一行起五个字符串和第二行起五个字符串是匹配的（即），只有最后一个不匹配。我们将像上面一样继续拆分成，这样就可以继续和第二行的匹配。以此类推，最后只剩下两个字符不能匹配，是不可能包含这两个字符的，因为。

注意需要使用高精度。

实现

核心代码：

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