Description

给你$n$个闭区间（第$i$个为$[l_i, r_i]$），要求你选出其中$m$个，使得他们的交集非空。

你的得分是选出区间中最长的和最短的的长度差。请求出最优解，无解输出$-1$。

$m\leq 200000, 1\leq m\leq n\leq 500000, 0\leq l_i\leq r_i\leq 10^9$。

Description

有一棵高$n$的完全二叉树，每个点可以染成黑色或者白色，黑叶子最多有$m$个。

如果一个叶子$i$和他的第$j$级别祖先都是黑的，那么会有一个$w_{i, j}$的收益。若都是白色，则有$f_{i, j}$的收益。求最大收益。

$1\leq n\leq 10, m\leq 2^{n - 1}, 0\leq w_{i, j}, f_{i, j}\leq 2000$。

Description

对于一个$n$个元素集合的所有子集，我们要从这些子集中取出至少一个，使得取出的集合的交的大小恰好为$k$。求方案数，答案对$10^9+7$取模。

$1\leq n\leq 10^6, 0\leq k\leq n$。

Description

有三个字符串$A,B,C$，他们都由小写字母和问号组成，其中问号可以代表任意小写字母。

已知在字典序上有$A<B<C$（这里的小于是严格小于），求有多少种问号填充能满足条件。

多组数据，$1\leq |A|,|B|,|C|\leq 10^6$。

Description

有$n$个球排成一列，初始时都为白色。

每次操作都从所有可能的区间里等概率选择一个，将其中的球都染黑。直到所有球都染黑，这个游戏才结束。

求期望的操作次数。

$T$组数据（$T\leq 50$），$1\leq n\leq 50$。

近期看了一些先辈的文章……柑橘要刷一些CC力，，，

怕不是有一半题都是毒瘤数据结构？

Description

有一个$n$个无色点的树，小红和小蓝二人在上面玩游戏。

游戏有很多轮，小红先手，然后两人轮替操作。每一轮操作者都必须将一个无色点染成自己的颜色，最后操作者的得分就是他自己染色的点的导出子图的连通块数量。

双方都想最大化自己和对方的得分差距，并且双方都一定采取最优策略。求最后小红和小蓝得分之差。

$1\leq n\leq 2\times 10^5$。

Description

有一个图有$n$个树形连通块，第$i$个有$a_i$个点。你需要再连$n - 1$条边使得这个图变成一个树。

对于一个方案$T$，我们记$d_i$表示第$i$个连通块向外连了多少边。那么我们称其价值为： $$\mathrm{val}(T) = (\sum_{i = 1}^n d_i^m)(\prod_{i = 1}^n d_i^m)$$ 其中$m$为给定常数。求所有可能的树的价值之和。

$n\leq 30000, m\leq 30, a_i\in Z_{998244353}$。

Description

有一个$n$个点的树，有一个固定的点为$x$。

$Q$次询问，每次给你一个集合。要求你求出从$x$出发，每一步都等概率随机选择一条邻边走过去，将集合中每个点都走了至少一遍的话期望的步数为多少（$x$视为一开始就经过了）。答案模$998244353$输出。

$1\leq n\leq 18, Q\leq 5000$。

Description

有$n$个人，第$i$人有一个正整数权值$w_i$。

每个人死后要开枪打死另一个人，假设剩下的人权值和为$S$，那么编号为$i$的活人被选中的概率为$\frac{w_i}{S}$。至于第一枪的话，随机选择一个人，第$i$个人被选中的概率为$\frac{w_i}{\sum_{i = 1}^nw_i}$。

问编号为$1$的人有多少概率成为最后一个死的人。

$\sum_{i = 1}^n w_i\leq 10^5$。