城市天际线
题面
构造一个有 $n$ 个点 $m$ 条边的简单有向图 , 恰好有 $X$ 个 SCC ( 强连通分量 ) . $q$ 个限制每个限制要求 $2$ 个点 ( $a_u$ , $a_v$ ) 在同一 SCC .
$\text{解题思路}$
用并查集维护 ( $a_u$ , $a_v$ ) 的限制 . 设连通块按大小排序为 $s_1$ , $s_2$ . . . $s_k$ , 当 $k > X$ 时无解 . 否则将最大的 $X - k + 1$ 个 SCC 合并 , 得到最多的边 . 设大小为 $t$ 的连通块的边的范围为 $[t,t(t - 1)]$ , 大小为 $x$ , $y$ 的连通块之间的边数为 $[0,xy]$ , 判断上下界 .
排列
题面
定义 $f(n)$ 的值为满足下列长度为 $n$ 的排列 $p$ 的个数 :
$$p_1 = 1 \land \forall i < n,\lvert a_i - a_{i + 1} \rvert \le 2$$
给定 $T$ 组询问 , 回答每个询问 $f(n)$ 的值 ( $mod\ 1e9 + 7$ ) .
求所有值的异或和 .
解题思路
$p_1 = 1$ , $p_2 \in {2,3}$ . 分类讨论 :
1 . $p_2 = 2$ , 方案数为 $f(n - 1)$ .
2 . $p_2 = 3$ :
- $p_3 = 2$ , 必有 $p_4 = 4$ , 方案为 $f(n - 3)$ .
- $p_3 = 5$ , 有且仅有唯一方案 $[1,3,5,7\ .\ .\ .\ 2k + 1,2k,2k - 1\ .\ .\ .\ 4,2]$ .
有 :
$$f(n) = f(n - 1) + f(n - 3) + 1$$
换元优化一下矩阵快速幂 .