给定 $n,p$，求有多少个 $\{1,2,3,\dots,n\}$ 的子集 $S$，满足 $\forall 1\le x\le n,\exist T\subseteq S,x=\sum\limits_{y\in T} y$，对给定正整数 $p$ 取模。

也就是求有多少个子集 $S$ 满足其 01 背包可以表示出 $[1,n]$ 中的所有数。

$1\le n\le 5\times 10^5,2\le p\le 1.01\times 10^9$，时限 $3$ s。

给定一张 $n$ 个点 $m$ 条边的 DAG，每条边 $u_i\to v_i$ 都满足 $u_i<v_i$。

点有五种类型：

1. 无特殊事件；
2. 走到这里会获得一个二元组 $(a,b)$；
3. 走到这里可以选择一个之前获得的二元组，将其的 $a$ 增加 $x$；
4. 走到这里可以选择一个之前获得的二元组，将其的 $b$ 增加 $x$；
5. 走到这里会获得一个数 $w$；

你要从点 $1$ 走到点 $n$，保证点 $1$ 和点 $n$ 是 $1$ 类点。

走到点 $n$ 时可以选择一个之前获得的二元组，将其的 $b$ 乘上 $10^9$。

最大化最终获得的所有二元组的 $a\times b$ 的和加上获得的数 $w$ 的和。

$1\le n\le 200$，$1\le m\le \min(\frac{n(n-1)}{2},2000)$，$1\le a,b,x\le 200$，$1\le w\le 10^6$。

给定 $n,m$ 和一个 $n\times m$ 的非负整数矩阵 $a$，$a_{i,j}\in [0,100]$。

根据这个矩阵构造一个二分图，其有 $n$ 个左部点和 $m$ 个右部点，连接第 $i$ 个左部点和第 $j$ 个右部点的无向边 $(i,j)$ 有 $\frac{a_{i,j}}{100}$ 的概率存在。

求这个二分图的最大匹配大小的期望。

$1\le n,m\le 9$。

如下定义一棵树的海胆度：

• 一个单点的海胆度是 $0$；
• 一棵树的海胆度是最小的 $k$ 满足删掉其某个节点后剩下的连通块的海胆度都 $\le k-1$；

给定一棵 $n$ 个点的树，求它的海胆度。

$1\le n\le 10^5$。

对于一个长 $m$ 的 $01$ 序列 $a_{[1,m]}$，定义变换 $f$：

• $f(a)_i=\left(\sum\limits_{j\le i}a_j\right)\text{ mod 2}$；

也就是做一次异或意义下的前缀和。

对于两个长 $m$ 的序列 $a,b$，定义 $g(a,b)$ 为：

• 至少对 $a$ 做多少次变换 $f$ 才能令 $\forall i,a_i=b_i$，如果无论做多少次变换都不可能，那么 $g(a,b)$ 为 $0$；

现在给定 $n$ 个长 $m$ 的序列 $a_{[1,n]}$，求 $\sum\limits_{i<j}g(a_i,a_j)$，对 $998244353$ 取模。

$1\le n\times m\le 10^6$，$a_{i,j}\in \{0,1\}$。

有一个 $n$ 个点的带权有向图，刚开始：

• $\forall 1\le i<n$ 存在边 $i\to i+1$，边权为 $0$，这些边不可删除；
• $\forall 1\le i<j\le n$，存在边 $i\to j$，边权为 $-1$；
• $\forall 1\le i<j\le n$，存在边 $j\to i$，边权为 $1$；

给定 $n\times n$ 的正整数矩阵 $A$，删除可删除的 $i\to j$ 的有向边的代价为 $A_{i,j}$，求最小的代价使得图中不存在负环。

$1\le n\le 500$。

有 $n$ 个人在一条数轴上，第 $i$ 个人位于 $X_i$。

每个人手中有一个烟花，每一个烟花可以燃烧 $T$ 秒。（可加强到每个人烟花燃烧时间不同）

第 $0$ 秒时，第 $k$ 个人的烟花开始燃烧。

人们可以在数轴上以相同的速度 $s$ 奔跑（即每秒奔跑 $s$ 个单位）。当两个人位于同一个位置，并且某一个人手中的烟花是点燃状态且另一个人手中的烟花未点燃，那么他们可以选择是否传火，即点燃另一个人手中的烟花。

求最小的非负整数 $s$ 使得所有人的烟花都可以被点燃。

$1\le n\le 10^5$，$0\le X_i,T\le 10^9$，$X_i\le X_{i+1}$。