MOD = 1_000_000_007 # a @ b，其中 @ 是矩阵乘法 def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]: return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zi…

O(n)时间处理查询回文串问题 # 将 dfsStr 改造为 t，这样就不需要讨论 n 的奇偶性，因为新串 t 的每个回文子串都是奇回文串（都有回文中心） # dfsStr 和 t 的下标转换关系： # (dfsStr_i+1)*2 = ti # ti/2-1 = dfsStr_i # ti 为偶数，对应奇回文串（从 2 开始） # ti 为奇数，…