题目

方程

解题思路

递推式

所以得到：

这是一个二阶线性递推关系。比如斐波那契数列就是这种形式（k=1）：

而这里是一般情况，系数是 ​k。

我们已经有：

• ​ f_1 = x + \frac{1}{x} = k
• ​ f_0 = x^0 + \frac{1}{x^0} = 1 + 1 = 2

所以：

• ​ f_0 = 2
• ​ f_1 = k
• ​ f_2 = k f_1 - f_0 = k^2 - 2
• ​ f_3 = k f_2 - f_1 = k(k^2 - 2) - k = k^3 - 3k
• ……

我们的目标是：快速计算第 n 项 ​f_n，特别是当 n 很大时（比如 ​10^9），不能一个一个算，要用更快的方法。

为什么要写成矩阵形式？

因为 矩阵可以用来“打包”多个变量，而且矩阵乘法可以“压缩”多次递推的过程。

关键思想：

把两个连续的项 ​f_n 和 ​f_{n-1} 看作一个向量：

然后我们希望找到一个矩阵 ​A，使得：

这样，每一步递推就变成了一次矩阵乘法。

如何构造这个矩阵？

我们从原始递推式出发：

同时，我们知道：

所以我们可以把两个等式写在一起：

这就可以写成矩阵乘法的形式：

我们发现：

其中 ​A = \begin{bmatrix} k & -1 \\ 1 & 0 \end{bmatrix}

所以只要我们能快速计算矩阵 ​A 的幂（比如用快速幂算法），就能在 ​O(\log n) 时间内求出 ​f_n

快速幂优化

• 矩阵快速幂时间复杂度 ​O(\log n)，远优于暴力递推 ​O(n)
• 核心思想：利用二进制分解幂次，将 ​n-1 次递推压缩为 ​\log_2(n-1) 次矩阵乘法
• 例如：​n=10^9 时只需约 30 次矩阵乘法

参考代码

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007; // 模数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long n = sc.nextLong();
            long k = sc.nextLong();

            // 边界情况：n=1 直接输出 k
            if (n == 1) {
                System.out.println(k % MOD);
                return;
            }

            // 构造转移矩阵 A = [[k, -1], [1, 0]]
            long[][] A = {
                    {k, -1},
                    {1, 0}
            };

            // 计算 A^(n-1) （矩阵快速幂）
            long[][] A_exp = matrixPower(A, n - 1);

            // f_n = A_exp[0][0] * f1 + A_exp[0][1] * f0
            // f1 = k, f0 = 2
            long fn = (A_exp[0][0] * k + A_exp[0][1] * 2) % MOD;
            // 负数取模处理
            fn = (fn + MOD) % MOD; // 确保 fn >= 0
            System.out.println(fn);
        }
    }

    // 矩阵快速幂：计算 matrix^power
    static long[][] matrixPower(long[][] matrix, long power) {
        // 初始化结果为单位矩阵
        long[][] result = {
                {1, 0},
                {0, 1}
        };
        long[][] base = matrix;

        while (power > 0) {
            // 当幂次为奇数时，将当前结果乘以 base
            if ((power & 1) == 1) {
                result = multiply(result, base);
            }
            // base = base * base，base 自乘（幂次减半）
            base = multiply(base, base);
            power >>= 1; // 位运算等价于 power /= 2
        }
        return result;
    }

    // 2x2 矩阵乘法（带模运算）
    static long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                long sum = 0;
                // 计算 C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j]
                for (int k = 0; k < 2; k++) {
                    sum = (sum + A[i][k] * B[k][j]) % MOD;
                }
                // % 负数会返回负数，所以需要调整
                C[i][j] = (sum % MOD + MOD) % MOD;
            }
        }
        return C;
    }
}

字符串哈希匹配字符串2

解题思路(双哈希防冲突)

问题分析

• 核心挑战：直接比较子串需O(n)时间，q次查询会超时（n,q≤10^5）
• 关键观察：子串相等等价于子串哈希值相等
• 难点：单哈希存在冲突风险，需用双哈希降低冲突概率

解法思路

1. 预处理前缀哈希：
   • 构建两个哈希数组（双哈希），分别用不同底数/模数
   • 预处理幂次数组（快速计算子串哈希）
2. 子串哈希计算：
   • 任意子串 [l, r] 哈希 = hash[r] - hash[l-1]*pow[r-l+1]
   • 用双哈希同时验证两个值
3. 查询处理：
   • 每次查询O(1)时间比较两个子串哈希
   • 双哈希同时匹配才认为相等

关键点

• 双哈希必要性：单哈希冲突概率10⁻⁹，双哈希降至10⁻¹⁸（实际无冲突）
• 负数取模：Java中 %会返回负数，需 (x % mod + mod) % mod处理
• 字符映射：'a'→1, 'b'→2, ... 'z'→26（避免'a'=0导致冲突）
• 底数选择：131/137（质数，避免与字符串特征相关）

字符串哈希的原理

基本思想：把字符串看成数字

想象一下，把字符串"abc"看成一个3进制数：

a = 1, b = 2, c = 3
"abc" = 1*3² + 2*3¹ + 3*3⁰ = 9 + 6 + 3 = 18

但通常我们用131进制（或其他大质数）：

a = 1, b = 2, c = 3
"abc" = 1*131² + 2*131¹ + 3*131⁰

为什么用131？

• 131是质数，能减少冲突概率
• 131比字母表大小（26）大，避免简单冲突

前缀哈希数组（关键）

如果我们想快速计算任意子串的哈希值，需要预处理前缀哈希数组。

定义：

• hash[i] 表示字符串前i个字符的哈希值
• hash[0] = 0
• hash[1] = s[0]
• hash[2] = s[0]*131 + s[1]
• hash[3] = s[0]*131² + s[1]*131 + s[2]
• ...

计算子串哈希值：

s[l...r]的哈希值 = hash[r] - hash[l-1]*131^(r-l+1)

参考代码

import java.util.*;
import java.io.*;

public class Main {
    static final long MOD1 = 1_000_000_007;  // 第一个模数
    static final long MOD2 = 1_000_000_009;  // 第二个模数
    static final long BASE1 = 131;  // 第一个底数
    static final long BASE2 = 137;  // 第二个底数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        String s = sc.next();

        // 预处理：前缀哈希 + 幂次数组
        long[] hash1 = new long[n + 1];
        long[] hash2 = new long[n + 1];
        long[] pow1 = new long[n + 1];
        long[] pow2 = new long[n + 1];

        // 初始化幂次数组和哈希数组
        pow1[0] = 1;
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow1[i] = (pow1[i - 1] * BASE1) % MOD1;
            pow2[i] = (pow2[i - 1] * BASE2) % MOD2;

            // 字符 'a' -> 1, 'b'->2, ... 'z'->26
            int charVal = s.charAt(i - 1) - 'a' + 1;
            hash1[i] = (hash1[i - 1] * BASE1 + charVal) % MOD1;
            hash2[i] = (hash2[i - 1] * BASE2 + charVal) % MOD2;
        }

        // 处理查询
        for (int i = 0; i < q; i++) {
            int l1 = sc.nextInt();
            int r1 = sc.nextInt();
            int l2 = sc.nextInt();
            int r2 = sc.nextInt();

            // 计算子串 [l, r] 的哈希值（双哈希）
            long h1_1 = getHash(hash1, pow1, l1, r1, MOD1);
            long h1_2 = getHash(hash1, pow1, l2, r2, MOD1);
            long h2_1 = getHash(hash2, pow2, l1, r1, MOD2);
            long h2_2 = getHash(hash2, pow2, l2, r2, MOD2);

            // 双哈希都相等才认为相等
            if (h1_1 == h1_2 && h2_1 == h2_2) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    // 计算子串 [l, r] 的哈希值
    static long getHash(long[] hash, long[] pow, int l, int r, long mod) {
        // 注意：l, r 是 1-indexed
        // 哈希公式: hash[r] - hash[l-1] * pow[r-l+1]
        long res = (hash[r] - hash[l - 1] * pow[r - l + 1]) % mod;
        // 处理负数取模
        return (res + mod) % mod;
    }
}

小蓝的字符串约数难题

解题思路(前缀函数（π函数）)

什么是前缀函数（π函数）？

• 定义：对于字符串 s，π[i] 表示子串 s[0..i] 的最长相等真前缀和真后缀的长度。
• 关键点：
  • "真" 意味着不能是整个子串本身（必须严格短于 s[0..i]）
  • "相等" 指前缀和后缀内容完全相同

💡 举个例子：字符串 "ababab"

• π[0] = 0（单字符无真前后缀）
• π[1] = 0（"ab" 的前缀"a" ≠ 后缀"b"）
• π[2] = 1（"aba" 的前缀"a" = 后缀"a"）
• π[3] = 2（"abab" 的前缀"ab" = 后缀"ab"）
• π[4] = 3（"ababa" 的前缀"aba" = 后缀"aba"）
• π[5] = 4（"ababab" 的前缀"abab" = 后缀"abab"）

π函数 vs 传统next数组

• 传统next数组：通常定义为 next[i] = π[i-1]（有移位）
• π函数优势：直接对应字符串特性，无需移位处理，逻辑更清晰
• 核心公式：最小周期 p = n - π[n-1]（当 n % p == 0 时）

KMP中的π函数应用（以字符串匹配为例）

π函数在KMP匹配中的经典用法：

public int strStr(String main, String pattern) {
    // 拼接 pattern + '#' + main
    String s = pattern + "#" + main;
    // pi 数组：pi[i] 表示 s[0..i] 的最长相等真前缀和真后缀长度
    int[] pi = new int[s.length()];
  
    for (int i = 1; i < s.length(); i++) {
        int len = pi[i - 1]; // 上一个位置的 pi 值
        // 当前字符不匹配时，回退到 pi[len-1]
        while (len > 0 && s.charAt(i) != s.charAt(len)) {
            len = pi[len - 1];
        }
        // 如果当前字符匹配，则长度加一
        if (s.charAt(i) == s.charAt(len)) {
            len++;
        }
        pi[i] = len;
    
        // 如果当前 pi 值等于 pattern 长度，说明找到了完整匹配
        if (pi[i] == m) {
            // 匹配位置：i - m（因为 s 是 pattern + # + main）
            // 减去 m*2 是为了跳过 pattern 和 # 的部分
            return i - m * 2;
        }
    }
    // 没有找到匹配
    return -1;
}

关键理解：

1. 拼接技巧：pattern + '#' + main 确保匹配不会跨越边界
2. π值含义：pi[i] 表示当前位置与 pattern 开头的匹配长度
3. 匹配条件：当 pi[i] == pattern.length() 时找到完整匹配

⚠️ 注意：这道题的重点不是KMP匹配，而是π函数本身揭示的字符串周期性！

如何用π函数解决公约数问题？

核心洞察：π函数直接给出了字符串的最小周期信息

1. 计算最小周期：

   • 对字符串 s（长度 n），计算 π[n-1]
   • 最小周期 p = n - π[n-1]
     • 物理意义：pi[n-1] 是整个字符串的最长自我匹配长度
       → 剩余部分 n - pi[n-1] 就是最小重复单元
     • 验证：s = "abababab" → pi[7] = 6 → p = 2（"ab" 是最小周期）
   • 验证条件：只有当 n % p == 0 时，p 才是有效周期

2. 约数长度的数学条件：

   • 任何约数长度 L 必须满足：
     • L 是 n 的约数（n % L == 0）
     • L 是 p 的倍数（L % p == 0）
   • 为什么？因为最小周期是 p，所以约数必须包含整数个 p

3. 算法步骤：

   • 对两个字符串分别计算有效约数长度集合
   • 求两个集合的交集大小

🔑 重点强调：这道题的本质是利用π函数分析字符串周期性，KMP只是π函数的一个应用场景，而非解题核心！

参考代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();

        // 获取两个字符串的约数长度集合
        Set<Integer> divisors1 = getDivisors(s1);
        Set<Integer> divisors2 = getDivisors(s2);

        // 求交集大小（公共约数个数）
        divisors1.retainAll(divisors2);
        System.out.println(divisors1.size());
//        // 也可以手动求交集：保留 divisors1 中也在 divisors2 中的元素
//        Set<Integer> intersection = new HashSet<>();
//        for (int d : divisors1) {
//            if (divisors2.contains(d)) {
//                intersection.add(d);
//            }
//        }
//
//        System.out.println(intersection.size());
    }

    // 获取字符串的所有约数长度
    private static Set<Integer> getDivisors(String s) {
        int n = s.length();
        if (n == 0) return new HashSet<>();

        // 步骤1: 计算前缀函数 π (标准π函数)
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int len = pi[i - 1];
            // 回退到更短的匹配前缀
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = pi[len - 1];
            }
            // 匹配成功，扩展长度
            if (s.charAt(i) == s.charAt(len)) {
                len++;
            }
            pi[i] = len;
        }

        // 步骤2: 计算最小周期 p
        int p = n - pi[n - 1];

        // 步骤3: 筛选有效约数长度
        Set<Integer> divisors = new HashSet<>();
        if (n % p != 0) {
            // 不能被分割，仅自身是约数
            divisors.add(n);
            return divisors;
        }
        // 找出 n 的所有约数，筛选能被 p 整除的
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // i 是约数
                if (i % p == 0) divisors.add(i);
                // n/i 是约数
                if ((n / i) % p == 0) divisors.add(n / i);
            }
        }
        return divisors;
    }
}

为什么这道题重点是π函数而非KMP？

KMP是π函数的应用，π函数是字符串周期性的体现，周期性是解题的关键！
这道题让我们看到：同一个算法组件（π函数）可以在不同场景发挥不同作用。