终于整完了 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]$表示有多少个 $i
m$的矩阵的秩为 $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

分类: 文章

2 条评论

XZYQvQ · 2018年6月23日 11:39 上午

emmm
您居然成功在我折腾数据库的期间写了一篇文章还成功发上来了
QvQ

    Annoyrain · 2018年6月23日 11:41 上午

    我说编辑的时候怎么这么奇怪……(其实是在 leanote 上写好了直接复制到这里来的

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注