BZOJ1494 [NOI2007] 生成树计数

Description 有一个 $n$ 个点的图。$n$ 个点排成一排,两个点之间有边当且仅当它们距离不超过 $k$ (即它们之间隔了不超过 $k-1$ 个点)。 求这个图的生成树个数。 $n\leqslant10^{15}, k\leqslant5$ 。 ...

BZOJ4944 [NOI2017] 泳池

Description 有一个底边长 $n$ 个单位,高为 $+\infty$ 的矩形网格,其中每个格子都有可能是危险的或者安全的。 每个格子安全的概率为 $p$ ,危险的概率为 $1 - p$ 。任意两个格子是否安全都是独立的。 要选取一个子矩形,要求它与底边相邻且其中所有格子都是安全的。最大化选取子矩形的面积。求答案恰好为 $k$ 的概率。 $n \leqslant 10^9, k \leqslant 1000$ 。 ...