Google Codejam KickStart 2017 Round G

https://code.google.com/codejam/contest/3254486/dashboard

具体Java代码可参见 https://github.com/ckcz123/codejam

Problem A. Huge Numbers

我们要计算a^(n!) mod p的值,其中a,n,p<=10^5。

对于Small(n<=10),直接计算即可。下面说Large。

我们只考虑n>=5的情况,n<5直接计算即可。 自然,我们会想到欧拉定理

a^φ(n) ≡ 1 (mod n)

但是,欧拉定理的使用是有条件的,要求(a,n)=1;但是在这题中,很明显a和p不一定互素,因此不能直接把欧拉定理往上套。

所以,我们可以先对p进行质因数分解:

p = p1^r1*p2^r2*...*pk^rk

然后对于每个素数pi,考虑是pi是否整除a:

  • 如果能整除,我们注意到n>=5,5!=120,所以pi^ri|a^(n!)。
  • 如果不能整除,则(pi^ri, a)=1;根据欧拉定理,我们有:
    a^(ri*(pi-1)) ≡ 1 (mod pi^ri)

    因此,只需要计算n!模ri*(pi-1)的余数即可。

故对于每个pi,我们都可以计算出a^(n!)模pi^ri的余数;最后从0遍历到p-1,找到x同样能得到相同的余数即可。

Problem B. Cards Game

这一题题目很长,简单而言,就是盒子内存在N张卡,每张卡有红黑两面,各有一个值。每一次你可以从中选出一张卡,选择其红面的值以及盒子内的某张卡的黑面的值去异或,或者其黑面的值以及盒子内的某张卡的红面的值去异或;重复这个操作直到盒子内最后只剩下一张卡为止,求所有这些异或值的和的最小值。

直接做不太好做,所以我们可以倒过来考虑:初始时盒子内只有一张卡,每次往盒子里面放一张,同时加上其红和盒子里某黑或其黑和盒子里某红的异或值,直到N张卡片全部放入盒子为止。

可以使用贪心算法:

  1. 对盒子内最后剩下的一张卡片进行枚举。
  2. 每一次,对于每一张还没放入的卡片,对于盒子里的每一张已经存在的卡片,找到一个最小的异或值;将那个还没放入的卡片放入盒子。
  3. 重复2,直到所有卡片都被放入了盒子为止。

Problem C. Matrix Cutting

非常简单的一个题,动态规划即可。

我们先计算对于原矩阵中每个子矩阵的最小值;然后动态规划计算每个子矩阵能切割后得到的最大值。

注意循环时最好从“差值”循环,以保证所有子状态都在之前被计算过。

[java]
1
2
3
4
5
6
7
for (int row_delta = 0; row_delta < n; row_delta++) {
    for (int top = 0; top < n - row_delta; top++) {
        int bottom = top + row_delta;
        // similar to the column
        ...
    }
}