Google Kickstart 2017 Round G，当时参加了Google招聘的云中讲堂，建议我们刷一刷Round G。然后就被虐了，只过了A和BC的小数据，55分Rk338滚粗。今天重新做了下，发现其实并不是很难，关键还是手速和脑子要快。

A. Huge Numbers

首先快速幂算阶乘的时候用了< n，完美地WA了两发，快速幂过了小数据，用祖传的公式过了大数据。
$$
A^x = A^{x mod \phi(c) + \phi(c)} (mod c) \\
x \ge \phi(c)
$$
后来看题解发现可以将$A^{N!}$展开成
$$
A^{1^{2^{3…}}}
$$
的形式，然后递归地来做。
AC代码

这边额外说一下这个$\phi$函数，也就是欧拉函数，表示小于n的与n互质的数的数量。欧拉函数的计算有如下公式
$$
\phi(n) = p^k - p^{k - 1}
$$
其中$p$表示$n$的所有质因子。
为了理解这个公式，我们首先假设$n$可以表示为一个p的k次幂。那么与$n = p ^ k$不互质的数就是所有的p的倍数，这样的数有$p ^ k / p$个。下面我们可以通过中国剩余定理得到欧拉函数是积性的，也就是说$\phi(i*j) = \phi(i) \, \phi(j)$。
不过在日常编码中，我们常使用递推来求欧拉函数。

B. Cards Game

有N个卡片，正反各有一个正整数。玩家初始分数0分，每次选两张卡片，分别将其中一张的正面和另一张的反面异或，并将结果加到总分上。结束后将一张卡片丢弃，另一张放回，由此重复一直到只有一张卡片。求最终最小的分数。
没有经受住过小数据的诱惑，直接爆搜了下，复杂度$O(2^N * N^2)$。
查看题解，题解使用图论的观点来看，由于每次操作都有一张卡片被消去，我们假设卡片$i$被$j$消去，可以看做从$i$到$j$存在一条边。
于是恍然大悟，这条就是个最小生成树啊，套个模板就出来了。注意大数据需要用LL。
AC代码

C. Matrix Cutting

有一个N*M的矩阵，现在按照行或列切分矩阵，每次讲一个大矩阵切分为两个小矩阵，就奖励原矩阵中的最小值对应的分数。整个过程一直以得到N*M个1*1的矩阵为止，求可能得到的最多分数。
这条小数据只有一行哎，于是暴搜（都可以不加记忆化）过了小数据。
大数据看起来有可以用二维线段树做，不过由于本人还是太弱，所以最后没时间做了。后来发现可以直接套用二维记忆化搜索强行莽掉。
AC代码
在实际跑的时候，常数太大了，我用VS开Release才能在6分钟左右算完。我打算写一个CodejamSolver来多线程跑，然后再join。