「Codeforces 1156E」Special Segments of Permutation
题目链接:Codeforces 1156E
你有一个长度为 $n$ 的排列 $p$,假如 $p_l + p_r = \max_{i = l} ^ r p_i$,那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。
数据范围:$3 \le n \le 2 \times 10 ^ 5$。
题目链接:Codeforces 1156E
你有一个长度为 $n$ 的排列 $p$,假如 $p_l + p_r = \max_{i = l} ^ r p_i$,那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。
数据范围:$3 \le n \le 2 \times 10 ^ 5$。
题目链接:LOJ 3083
Freda 学习了位运算和矩阵以后,决定对这种简洁而优美的运算,以及蕴含深邃空间的结构进行更加深入的研究。
对于一个由非负整数构成的矩阵,她定义矩阵的 $\text{AND}$ 值为矩阵中所有数二进制 $\texttt{AND(&)}$ 的运算结果;定义矩阵的 $\texttt{OR}$ 值为矩阵中所有数二进制 $\texttt{OR(|)}$ 的运算结果。
给定一个 $n \times n$ 的矩阵,她希望求出:
接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题,所以这个问题就交给你了。
由于答案可能非常的大,你只需要输出答案对 $10 ^ 9 + 7$ 取模后的结果。
数据范围:$1 \le n \le 10 ^ 3$,$\text{矩阵中的自然数} \le 2 ^ {31} - 1$。
题目链接:POJ 3415
字符串 $T$ 的子串定义为:
$$ T(i,k) = T_iT_{i + 1}\cdots T_{t + k - 1}, 1 \le i \le i + k - 1 \le \lvert T \rvert $$
给定两个字符串 $A, B$ 和一个整数 $K$,我们定义 $S$ 为三元组 $(i, j, k)$ 集合:
$$ S = \{(i, j, k) \mid k \ge K, A(i, k) = B(j, k)\} $$
你需要求出集合 $S$ 的大小 $\lvert S \rvert$。
数据范围:$1 \le \lvert A \rvert, \lvert B \rvert \le 10 ^ 5$,$1 \le K \le \min(\lvert A \rvert, \lvert B \rvert)$。
题目链接:LOJ 2377
给定一个长度为 $n$ 的字符串 $S$,令 $T_i$ 表示它从第 $i$ 个字符开始的后缀,求:
$$ \sum_{1 \le i < j \le n} \text{len}(T_i) + \text{len}(T_j) - 2 \times \text{lcp}(T_i, T_j) $$
其中,$\text{len}(a)$ 表示字符串 $a$ 的长度,$\text{lcp}(a, b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。
数据范围:$2 \le n \le 5 \times 10 ^ 5$。