\[\large \text{Round 8 : AtCoder Beginner Contest 310 (VP)} \]
一言:
虚伪的眼泪，会伤害别人，虚伪的笑容，会伤害自己。
——反叛的鲁鲁修
\(\text{F}\) 竟然没有第一时间想到状压，还是太蒟了。。
\(\text{F: Make 10 Again}\)
这题看到一个子集，再加上子集和的范围只需要考虑小于 \(10\) 的情况，其实就应该直接想到状压的，不知道当时我是范什么抽了，竟然没想到。。。
我们定义 \(dp_{i,j}\) 表示前 \(i\) 个数中，每个骰子选出的数所能构造出的小于等于 \(10\) 的子集和只能是 \(j\) 状态上二进制为 \(1\) 的数。
显然，我们可以考虑枚举一个 \(k,l\) 分别表示第 \(i\) 个骰子会投出那个数。和从 \(i-1\) 的那个状态转移过来。那么下面就是考你位运算的时候。
首先已经至少出现 \(k\) 这个状态了，接着，由于投出了 \(l\)，所以当前状态就变成了 \(2^l | k\)。但是由于是子集和，所以以前的子集和可以全部加上 \(l\) 构成新的子集和，也就是 \(k<<l\)，但是由于这样可能会超出 \(10\)，所以有 \((k<<l) \& (2^{10}-1)\)，所以用人话说就是 \(dp[i][2^l|k|((k<<l) \& (2^{10}-1))]+=\dfrac{dp[i-1][k]}{a[i]}\)。
另外，对于 \(a_i \ge 10\) 的情况可能会导致左移的太多炸精度，所以直接特殊处理就可以了。
\(\text{G: Takahashi And Pass-The-Ball Game}\)
题目里面那个期望其实没什么大用的，就是用来唬人的。
仔细读题之后，就会发现题意实际上就是对于一个点 \(i\) 他的权值是 \(a_i\)，他的父亲是 \(b_i\)，他会对所有他 \(k\) 步以内的祖先的答案全部加上 \(a_i\)，最后输出每个点的答案除以 \(k\) 对一个质数取模。
由于是向上跳 \(k\) 步，我们考虑是否可以倍增。（鬼知道是怎么想到这个倍增的。）我们可以一步一步来理解这个过程：
如果是向上跳 \(2^j\) 步，且当前每个数组中已经存好了 \(2^{j-1}\) 步的情况。（具体储存什么后面会讲）注意，由于是倍增处理，我们要把 \(a\) 和 \(b\) 数组也处理到倍增以后的情况，也就是 \(a_i\) 就表示当前跳完 \(2^{j-1}\) 步后，他的 \(2^j\) 步会跳到哪里，所以跳完 \(2^{j-1}\)，都有 \(a_i=a_{a_i}\)。（仔细思考可以发现，这个和树上倍增的思想类似。）对于 \(b_i\)，我们储存已经跳完 \(2^{j-1}\) 步每个点的答案。仔细想可以发现，我们对于 \(b_i\) 只需要统计从 \((2^{j-1}+1)-2^j\) 这些步数跳来的，在加上 \(b_i\)，就可以得到答案。仔细思考一下，这不就是 \(b_{a_i}=b_{a_i}+b_i\)。
最后统计答案的时候，我们将所有 \(k\) 的二进制位是 \(1\) 的 \(b\) 加到答案上就可以了。（并记得在此时重新初始一下 \(b\) 数组）
还是要配合代码才能方便理解啊。。。。
\(\text{What I learned:}\)
-
当答案是关于选出的数的一些子集的限制时，且这些限制并不是很多，可以通过二进制表示出来。那么请考虑状态压缩。
-
当你在题目中看到期望的时候，不要紧张，大概率都需要将问题的模型转化一下。
-
如果要求 \(n\) 个东西经过 \(k\) 步的贡献之和，可以考虑把 \(k\) 拆成 \(2^{i_1}+2{i_2}+...2^{i_l}\) 这样一个一个的二进制位。然后从 \(2^0\) 开始，每次让次数加一次，也就是通过一些手段求出经过 \(2^0,2^1,2^n...2^{il}\) 这些步数的贡献，然后每次将 \(2^{i_1},2^{i_2}...2^{i_l}\) 这些步数的贡献加在一起，就可以得到 \(k\) 步的贡献之和。相当于将时间复杂度从 \(O(nk)\) 优化到 \(O(n \log k)\)。
-
不只是树可以倍增，仔细想想，基环树或者只有一个父亲的图是不是都可以倍增？