【题解】hihocoder 挑战赛 33 -annoyrain

终于整完了 QAQ
队爷 $0.5h\ AK$然而蒟蒻要花 $(N+1)\ hours$勉强明白

肯定是有很多错误的，欢迎指正 QAQ
那还是~~不~~欢迎线上/线下 dd 吧。

---

##【A】打怪
有 $n$个怪物，第 $i$个怪物的血量是 $a_i$，设这 $n$个怪物组成的集合为 T。
现在你有一个技能，发动一次需要花费一个金币，当技能发动后，所有存活的怪物的血量都会 $-1$，当怪物血量降为 $0$后视为被消灭。
特别的，如果这次发动的技能后有至少一只怪物死亡，你都将获得一个金币的奖励。
令 $f(S)$为消灭集合 S 中的怪物总共需要付出几个金币，即花费的金币数量减去获得的奖励金币数量。
求 $\sum_{S⊆T} f(S)$，答案对 $10^9+7$取模。
$1 \leq n \leq 10^5, 1\leq a_i \leq 10^9$

---

消灭掉一个集合 $S$内的怪物需要花费的金币为 $max_blood(S) – S$内不同的生命值的数量。
$g(S) = S$内最大的生命值，$h(S) = S$内不同生命值的数量。
两个函数单独都可以求。
排序之后 $g(S)$可以直接计算，$h(S) = \sum_{i=1}^n$选了 $a[i]$的集合的个数。

---

##【B】秩的问题
对于一个数组 $a[1..n]$，定义 $f(a[1..n])$为：最少能从 $a[1..n]$选多少个数 $b[1..c]$，使得每个 $a[i]$都能被表示成 $b[1..c]$中若干个数的异或值。
求对于所有满足 $0 ≤ a[i] < 2^m$的数组 $a[1..n]$，$f(a[1..n])$之和。
例如：$f([1,2,3])=2,f([0,0,0])=0$，答案对 $P$取模。
$n, m \leq 10^3, 1 < P \leq 10^9 + 7$

---

看到题目的时候满脑子线性 $gay$。
题意可以转化为：求模 $2$域下的 $nm$的矩阵的秩之和。
（线性 $gay$白学了连这个都能忘）
$f[i][j]$表示有多少个 $im$的矩阵的秩为 $j$。
如果矩阵的秩为 $j$的话那么显然有 $2^j$个数是可以被表示出来的。
所以 $f[i][j] = f[i-1][j]*2^j + f[i-1][j-1] * (2^m – 2^{j-1})$。

---

##【C】加减
对于一个数 $x$，设它最低位的 $1$是第 $i$位，则 $lowbit(x)=2^i$。
例如 $lowbit(5)=1$，$lowbit(12)=4$。
定义对 $x$的一次变换为：有 $50\%$的概率变成 $x+lowbit(x)$，有 $50\%$的概率变成 $x-lowbit(x)$。
定义 $f(x)$为对 $x$不停变换，变换到 $0$的期望变换次数。
给定 $L$, $R$，求 $\sum_{x = L} ^ R f(x)$。
答案对 $998244353$取模。
$0 \leq L \leq R < 2^{31}$

---

首先通过一系列势能分析可以发现通过奇偶性求 $f(x)$的复杂度是可以接受的。
因为 $lowbit$只会对末位的 $1$操作，所以 $x$最后面的 $0$都可以直接去掉。
当 $x$的末位为 $1$时，它有等概率转为 $x+1$和 $x-1$，$f(x-1)$与 $f(x/2)$是相同的，$f(x+1)$与 $f((x+1)/2)$时相同的。无论如何这里的复杂度是可以接受的
然后再根据奇妙的奇偶性分析发现可以递归求解。

\begin{eqnarray}
\sum_{i = l} ^ r f(x) &= 2 * \sum_{i = l} ^ r f(i)*[i\ Mod\ 2==0] + \sum_{i = l} ^r [i\ Mod\ 2 == 1]
\end{eqnarray}

在强制 $r, l$都是偶数之后，其中的 $f(l)$和 $f(r)$只会分别被 $f(l+1)$和 $f(r-1)$计算 $\frac{1}{2}$遍，所以最后要减去。

---

##【D】取数字
一开始你有 $n$个数，分别是 $1..n$，每轮你会等概率在还存在的数中随机选一个，然后把它的倍数全部删掉，求期望几轮能删完。
答案对质数 $P$取模。
$n\leq 10^9, P \leq 10^9 + 7$

---

不如将题目转化为：每次随机选择一个数删去，如果之前选择了它的约数，那么答案不变，否则答案 $+1$，求答案的期望。
每个数的期望贡献为 $\frac{1}{d(x)}$。
求 $\sum_{i=1}^n \frac{1}{d(x)}$。
~~表面笑嘻嘻内心 MMP~~
还专门去学了 min_25 筛 QAQ