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\)。