roll 制出题人.
大样例没有,小样例极水,权值范围也没有,题意还没说清楚.
$guard$
每个武器只能打死一个人.我以为能将小于等于它的的全部打死,就保龄了.
将所有武器按 $a$ 从小到大排序.
第一次枚举确定哪些武器用精灵,如果用精灵能打死的怪的 $b> a_i$ ,就用精灵打.
然后剩下的武器都不用精灵,直接贪心匹配.
时间复杂度 $O(T\cdot n\log n)$
$phase$
直接用树剖 + 线段树维护区间内所有点权值的异或和,时间复杂度是 $O(n\log^2 n)$ .
但用一下异或的性质,就能做到 $O(n\log n)$ .
记 $dist(i)$ 表示从 $i$ 到根节点的路径上经过的所有点权值异或和.
每次询问 $(x,y)$ ,先求出它们的 $lca$ ,答案就是 $dist(x)\text{ xor }dist(y)\text{ xor }dist(lca)\text{ xor }dist(fa(lca))$ .
树剖后用线段树来维护每个点的 $dist$ ,每次修改时,子树 $x$ 内深度奇偶性与 $x$ 不同的点 $dist$ 会被异或上 $y$ .
线段树中维护两个标记,分别表示深度为奇/偶的点需要异或上的值,时间复杂度 $O(n\log n)$ .
$refuse$
$50$ 分的做法是状压 $dp$ ,设 $f(r,c)$ 表示行覆盖情况为 $r$ ,列覆盖情况为 $c$ 时的期望,时间复杂度 $O(2^{n+m}\cdot nm)$ .
但不知道怎么回事写挂了,就保龄了.
下面是正解.
设 $f(i)$ 为恰好经过 $i$ 次操作后成功的概率,根据期望定义,答案 $ans=\sum_{i=0}^{+\infty} f(i)\cdot i$ .
再设 $P(i)$ 表示经过了 $i$ 次操作后还没有成功的概率.那么就等价于在之后成功的概率之和, $P(i)=\sum_{j=i+1}^{+\infty} f(i)$ .
可以发现 $ans=\sum_{i=0}^{+\infty} P(i)$ ,因为这样计算,每个 $f(i)$ 都恰好被计算了 $i$ 次.
于是需要考虑如何求出 $P(i)$ .
枚举哪些行和列在前 $i$ 次操作都没有被标记,记它们形成的集合为 $s$ .
设 $p(s)$ 表示选中集合 $s$ 中的行列中的格子 $1$ 的概率,那么 $i$ 次都没选中就是 $(1-p(s))^i$ ,利用容斥原理计算,
$$
P(i)=\sum_s (-1)^{|s|+1} \cdot (1-p(s))^i
$$
代入答案 $ans$ ,
$$
\begin{aligned}
ans&=\sum_{i=0}^{+\infty} P(i) \\
&=\sum_{i=0}^{+\infty} \sum_s (-1)^{|s|+1} \cdot (1-p(s))^i \\
&=\sum_s (-1)^{|s|+1}\cdot \frac 1 {p(s)}
\end{aligned}
$$
设 $tot$ 为格子 $1$ 的总数目, $sum(s)$ 表示集合 $s$ 的行列含有的 $1$ 的数目,那么答案为
$$
ans=\sum_{s}(-1)^{|s|+1}\cdot \frac {tot} {sum(s)}
$$
于是只需要计算 $sum(s)$ .因为 $sum(s)$ 相同的状态有很多,可以设 $num(x)=\sum_s [sum(s)=x]\cdot (-1)^{|s|+1}$ .
则答案为
$$
ans=\sum_{x=1}^{tot} num(x)\cdot \frac {tot} {x}
$$
考虑如何计算 $num(x)$ ,由于 $n\cdot m\le 200$ ,所以 $\min(n,m)\le 14$ .
假设 $n\le m$ ,否则只需交换行与列.
暴力 $2^n$ 枚举选了哪些行,对列做 $dp$ ,设 $dp(i,j,k)$ 表示考虑了前 $i$ 列, $|s|$ 的奇偶性为 $j$ , $sum(s)=k$ 的方案数.
最后根据奇偶性计算出每个 $num(x)$ ,统计答案即可.
时间复杂度为 $O(2^n\cdot m^2\cdot n )$ .