终于整完了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上写好了直接复制到这里来的

发表评论

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

你是机器人吗? =。= *