zxy:
P3750 [六省联考 2017] 分手是祝愿
有 \(n\) 个灯泡和 \(n\) 个开关，摁下第 \(i\) 个开关会影响所有编号为 \(i\) 的因数的灯泡的亮灭。初始状态下，灯泡有亮有灭。
小 A 按照如下方式操作：
-
若 \(k\) 步以内可以让灯泡全灭，则小 A 会执行最优操作之一；
-
否则小 A 会均匀随机选择一个开关摁下。
求小 A 将所有灯泡变成全灭的期望步数乘 \(n!\)，模 \(100003\)。
P3343 [ZJOI2015] 地震后的幻想乡
给定一个 \(n\) 点 \(m\) 边的无向图，每条边的权值为 \([0,1]\) 间均匀随机的实数，求该图最小生成树的边权最大值的期望。四舍五入保留 \(6\) 位小数。
\(n\le 10, m\le\frac{n(n-1)}{2},1\operatorname{s}/128\operatorname{MB}\)。
Hint
有 \(n\) 个 \([0,1]\) 间的随机实数，其中第 \(k\) 小的期望值为 \(\frac{k}{1+n}\)。
Bonus
尽可能简洁地证明 Hint。不准用积分。
CF717H Pokermon League Challenge
有 \(n\) 个人，第 \(i\) 个人都有 \(l_i\) 个想加入的队伍。
这 \(n\) 个人中的每个人都讨厌一些人，讨厌关系是双向的，讨厌关系总共有 \(m\) 组，并且没有人讨厌自己。
你要将这 \(n\) 个人分入队伍中并把这些队伍再分为红蓝两方，使得：
-
每个人都加入了自己想加入的队伍之一；
-
红方人员和蓝方人员之间的讨厌关系有至少 \(\lceil \frac{m}{2} \rceil\) 对；
-
每个人都在恰好一个队伍里，且每个队伍只能处于红蓝两方之一。
构造方案，或者输出无解诈骗的，有解。
\(4\le n\le 5\times 10^4, 2\le m\le 10^5, 16\le l_i\le 20, 5\operatorname{s}/256\operatorname{MB}\)。
CF1349F1 Slime and Sequences (Easy version)
对于一个序列 \(p\)，我们令其是好的当且仅当对于任意 \(i\geq 2\)，都有：
- 若 \(i\) 在 \(p\) 中出现，则 \(i-1\) 一定在 \(i\) 最后一次出现之前出现过。
对于序列 \(p\) 与正整数 \(i\)，令 \(f_p(i)\) 为 \(i\) 在 \(p\) 中的出现次数。给定 \(n\)，令 \(S_n\) 为所有长度为 \(n\) 的好序列的集合。对于所有 \(1\le i\le n\)，求
\(n\le 5000, 2\operatorname{s}/256\operatorname{MB}\)
wlx:
CF1264D2 Beautiful Bracket Sequence
给定一个长度为\(n\)的字符串，其中只有(, ), ?三种字符。
对于一个括号序列，定义其权值为其通过任意删除字符后可以得到的合法的括号匹配的最深深度。空串合法且权值为0。
请求出将所有?替换为(或者)得到的括号序列的权值和，答案对\(998244353\)取模。
\(n \le 10^6\)。
LOJ3053 「十二省联考 2019」希望
给你一棵 \(n\) 个点的树，让你找出 \(k\) 个彼此区分的连通块，使得这些连通块交集中存在一点到连通块并集中的任意一点的距离不超过 \(L\)。求方案数模 \(998244353\)。
\(1 \le n \le 10^6 , 0 \le L \le n , 1 \le k \le 10\)。
xmz:
CF1750G Doping
给出长度为 \(n\) 的排列 \(p\)，对 \(k \in [1,n]\) 求有多少排列字典序小于 \(p\)，且最多划分为 \(k\) 个公差为 \(1\) 的等差数列。 \(n \leq 2000\)
CF1621G Weighted Increasing Subsequences
定义序列 \(a_{i_1\cdots i_k}\) 的一个长度为 \(n\) 的上升子序列的权值为满足存在 \(x \in (i_k,n]\) 使得 \(a_x > a_{i_j}\) 的 \([1,k]\) 内的整数 \(j\) 的个数。求出 \(a\) 的所有上升子序列的权值和。\(n \leq 2 \times 10^5\)
ljy:
CF1781F - Bracket Insertion
Vika 有一个空串 \(s\)，她会进行如下操作 \(n\) 次：
随机 \(|s| + 1\) 个间隔中的一个，并插入两个括号（以 \(p\) 的概率插入「\(\texttt{()}\)」，以 \(1 - p\) 的概率插入「\(\texttt{)(}\)」）。
求生成的括号串合法的概率，对 \(998 \space 244 \space 353\) 取模。
\(n \le 500\)。
AGC020F - Arcs on a Circle
有一长为 \(C\) 的圆周。您在上面依次画出了 \(N\) 段弧。第 \(i\) 段弧的长度为 \(L_i\)。
每个弧会被画在独立均匀随机的位置。（所以，可能出现相交、包含等情况。）
求圆周上所有点都被覆盖的概率，请给出实数，要求绝对误差不超过 \(10^{-11}\)。
\(N \le 6\)，\(C \le 50\)。
wzy:
CF1515E Phoenix and Computers
现有 \(n\) 个电脑，初始时都关着，Phoenix 想把它们都打开。这些电脑有个机制，当电脑 \(i-1\) 和 \(i+1\) 都已打开且电脑 \(i\) 还未打开时，电脑 \(i\) 会自动打开。
求 Phoenix 有几种本质不同的方案打开所有电脑。两种方案本质不同当且仅当 Phoenix 手动打开电脑的序列不同。注意 Phoenix 不能再次打开一台已经自动打开了的电脑。\(n\le 400\)。
CF1781F Bracket Insertion
现在有一个括号序列，初始为空。你会进行 \(n\) 次操作，假设现在序列长度为 \(s\)，那么你会在 \(s+1\) 个空位中等概率随机一个位置，然后以 \(p\) 的概率插入一个 ()，以 \(1-p\) 的概率插入一个 )(。求最终括号序列合法的概率。\(n\le 500\)。