$Link$

给定一个长度为 $n$ 的排列 $a$，定义一个序列是合法的当且仅当被标记的数单调递增。

一开始，$a$ 中的每个数均未被标记，每次可以等概率选择一个未被标记过，且标记后序列合法的数标记，当没有可以选择的数时停止操作，求期望的标记个数，对 $10^9+7$ 取模。

$1\le n\le2000$。

$Link$

有一个两堆石子的 $Nim$ 游戏，但是多了 $n$ 个必败态 $(x_i,y_i)$，表示第一堆石子数为 $x_i$，第二堆石子为 $y_i$ 时，就无法执行任何操作了。（石子数量有序）

询问 $m$ 次，每次询问给你 $(a_i,b_i)$，你需要回答当第一堆石子数为 $a_i$，第二堆石子数为 $b_i$ 时，先手的胜负状态。

$1\le n,m\le10^5,0\le x_i,y_i,a_i,b_i\le10^9$。

$Link$

有一个 $01$ 串 $s$。

你可以执行任意多次操作，每次操作可以选择一段 $0$ 和 $1$ 个数相同的子串，然后把它翻转，再把其中的 $0$ 变成 $1$，$1$ 变成 $0$。

求可以得到的字典序最小的 $s$。

多组数据，$\sum|s|\le5\times10^5$。

$Link$

有一个 $n$ 个点 $m$ 条边的有向无环图，每次不断在 $[1,n+1]$ 内随机一个整数 $x$，如果 $x\le n$，就在点 $x$ 上放一个石子，否则停止放石子。

之后，两人在这个图上玩组合游戏，每次选择一个石子向出边移动到下一个点，不能移动者就输了。

问先手赢的概率，对 $99824353$ 取模。

$1\le n\le10^5,0\le m\le10^5$。

$Link$

有一棵 $n$ 个点的树，每个点上都有一个颜色。

有 $q$ 次询问，每次询问路径 $u\to v$ 上颜色编号在 $[l,r]$ 内的出现奇数次的颜色。如果存在，输出随意一个满足条件的颜色，否则输出 $-1$。

$1\le n,q\le3\times10^5$，时间限制 $5s$。

$Link$

有一个 $n$ 个点的无向图，对于每个点给出一个 $p_i$，表示 $i$ 和 $p_i$ 要在同一个联通分量内。

现在有一些点的 $p_i=-1$，表示还不确定。现在你要对于每种可能求出满足条件的最小的边数的和。

对 $10^9+7$ 取模。

$2\le N\le5000,p_i\not=i$。

$Link$

给定一个 $n$ 个点的无向图，第 $i$ 个点有 $d_i$ 个接口，每条边连接两个不同的点的接口，每个接口只能被一条边连接。问这张图的生成树个数，对 $998244353$ 取模。

$2\le n\le 2\times10^5,1\le d_i<998244353$。

$Link$

给定一个 $n$ 个点 $m$ 条边的简单无向图，每个点有 $a_i,b_i$ 两个权值。

定义一个联通块的价值为联通块中所有点的 $b_i$ 之和的绝对值，一个图的价值为这张图的所有极大联通块的价值和。

你可以以 $a_i$ 的代价删去第 $i$ 个点以及所有与它相连的边。

最大化图的价值 $-$ 代价。

$1\le n\le300,1\le m\le300,1\le a_i\le10^6,|b_i|\le10^6$。

$Link$

有两棵高度为 $h$ 的完全二叉树，每棵有 $2^h-1$ 个节点，称为红树和蓝树。它们的根节点编号为 $1$，并且 $x$ 的左儿子为 $2x$，右儿子为 $2x+1$。父亲和儿子之间有一条无向边连接。

红蓝树的叶子结点构成了一个双射，对应的节点间有一条无向边相连，称这些边为特殊边。

我们定义一个好的环，当且仅当这是一个简单环并且正好经过了两条特殊边。一个环的权值就是它经过的所有点的编号的乘积。

现在给你这个双射，问在这个由两棵完全二叉树和特殊边构成的图上的所有的好的环的权值和。

对 $10^9+7$ 取模。

$2\le h\le18$。

$Link$

有一个长度为 $n$ 的长度序列 $x$，一开始所有元素都是 $0$。你一次可以进行以下两种操作之一：

• 选择一个长度为 $k$ 的单调不降序列 $c$，把 $x_i$ 变为 $x_i+c_i$。

• 选择一个长度为 $k$ 的单调不升序列 $c$，把 $x_{n-k+i}$ 变为 $x_{n-k+i}+c_i$。

问最快多少次能把 $x$ 变为给定的序列 $a$。

$1\le n\le2\times10^5,1\le a_i\le 10^9$。