题解：[[2024.9.24 模拟赛]] ## 集合 #递推 #费马小定理 给定正整数 $n$，有集合 $S={1,2,\cdots,n}$，对于 $S$ 的子集 $s$，计算 $\prod s$，对 $998,244,353$ 取模。 ## 出租 #最大子段和 #线段树 有 $n$ 栋楼，编号 $1\sim n$，每栋楼 $k$ 个空房间，每房间住一人。对于喜好为 $x$ 的租客，它只能住在编号为 $x\sim x+d$ 的楼中。现有 $m$ 次询问，询问为 $(x,y)$ 的形式，表示来了 $y$ 个喜好为 $x$ 的租客，$y$ 为负代表租客离开。每次询问你要回答是否能住下所有租客。 ## 连通块 #树形dp 有一棵根为 $1$ 的树，点的编号为 $1\sim n$，第 $i$ 个点的权值为 $a_i$，dfs 序为 $d_i$。你需要在树上找到权值和最大的联通块，满足 $m$ 个 $(u,v)$ 的性质：$u,v$ 若同时存在于连通块内，则 $d_u$ 与 $d_v$ 不能相邻。输出最大和。 ## 跳棋 #序列dp #组合数学 有 $1\times n$ 的棋盘，每一个格子里最初的形式为 $0,1$ 或 $?$。$0$ 表示该格子没有棋子，$1$ 反之，$?$ 表示不知道。一个棋子可以跳过它旁边的棋子，到它旁边的棋子的下一个位置，仅当那个位置没有棋子。对于所有可能的开局，你可以操作若干包括 $0$ 步，问你每一种开局下面结束状态的数量，的和。