有一个 $(n + 2) \times m$ 的长方形，除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率被摧毁，每行之间独立且左边和右边独立，求 $k$ 天之后最上面一行与最下面一行四联通的概率。

其中 $1\le n,m\le 1500,\,0\le k\le 10^5$，答案对 $10^9+7$ 取模。

给一个长度为 $2n$ 的序列，要求将其两两匹配成 $n$ 组，假设第 $i$ 组为 $(x_i,y_i)$，求 $\max_{i=1}^n(x_i+y_i)\bmod m$ 的最小值，$1\le n\le 10^5,1\le m\le 10^9,0\le a_i<m$。

有一张二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点，$m$ 条边。每个点可能有一种颜色 R 或者 B，也可能没有，也就是 U。现在要给一些边染色，把边染成 R 要花费 $r$ 的代价，把边染成 B 要花费 $b$ 的代价，要求对于每个颜色为 R 的点，与之相邻的边中 R 的边严格多于 B 的边；对于每个颜色为 B 的点，与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案，输出任意一种，无解输出 $-1$。其中 $1 \le n_1, n_2, m, r, b \le 200$。

给你一棵 $k\ (k\le 30)$ 阶的满二叉树，从上到下、从左到右从 $1$ 开始编号，设 $\{p_{n}\}$ 是它的 Prüfer 序列。给你三个数 $a,d,m$，求 $\sum_{i=0}^{m-1}p_{a+id}$。

给定一个长度为$n$的字符串，其中只有 '(', ')', '?' 三种字符，其中 '?' 可以为 '(' 或者 ')'。对于一个括号序列，定义其权值为其通过删除字符后可以得到的合法的括号匹配的最深的深度，求出所有可能的括号序列（即问号替换后）的权值和。

在 D1 中，$n\le 2000$；在 D2 中，$n\le 10^6$。

感觉已经濒临AFO了。

题意大概就是有$n$个点，每个点其坐标$x_i,y_i$与权值$c_i$，其中$1\le n\le 5\cdot 10^5,0\le x_i,y_i\le 10^9,-10^6\le c_i\le 10^6$。

让你选一个正方形，该正方形的左下角及右上角必须在$y=x$这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边权。输出所获的最大权值及其选择正方形的左下角$x_1,y_1$及右上角$x_2,y_2$，要求$0\le x_1=y_1\le x_2=y_2\le 2\cdot 10^9$。

题目大意就是有$n\,(n\le 30)$个点的无向完全图，有$m\,\left(m\le \frac{n\times (n-1)}{2}\right)$条道路上没有怪兽，其他道路都有怪兽。

一个人一开始在$1$号点，每次会随机选择一条路走并把这条路上的怪兽全部杀完。

问期望走多少步才能让这$n$个点之间都存在没有怪兽的路径。

按照国际惯例，多组数据，$T\le 100$。

感觉tf的时候还是打几场VP好……

加*号的是当场过掉的，这样以后复习可以用。

决定开个新坑，刷一些CF上的dp题。

现在做了几题：