NOIP2015普及组第3题——sum

1. 原题

2. 解题思路

枚举所有的 x、z 再判断是否符合条件并求和，是大部分人都能想到的做法，不过只能拿到 40 分。其实这样的枚举方式是有优化余地的，题目要求的 x 和 z 必须是奇偶性相同的，否则不存在正整数 y 满足题意。另外 x 和 z 的颜色需要相同，因此只有奇偶性相同、颜色也相同的格子两两之间才会产生分数。

但这样还是不够快速，计算分数时其实不需要逐一枚举求和。( x + z ) · ( number_x + number_z ) = x · number_x + z · number_z + x · number_z + z · number_x，其中 x · number_x 只依赖于 x，可以预处理其累计和（d [ 颜色 ] [ 奇偶性 ]）。假设同一种颜色、奇偶性的格子一共有 s 个（可以预处理计算），那么每个 x · number_x 都在分数和中出现了 ( s - 1 ) 次，即和其他的 s - 1 个格子作为 x 和 z 配对产生的和（x < z，任何 2 个格子只可能产生 1 次和）。

z · number_x 对于同一个 x 来说，其和为 number_x · ( sum ( 编号 ) - x )，先将其补上一个 number_x · x。那么此时这部分和为 sum ( number ) · sum ( 编号 )，sum ( number ) 和 sum ( 编号 ) 都是可以预处理的。需要减去的 number_x · x 算在之前的 ( s - 1 ) · sum ( number_x · x )，于是变为 ( s - 2 ) · sum ( number_x · x )。

不过似乎少了 x · number_z，其实也被算在了 number_z · ( sum ( 编号 ) - z ) 中了，最后不要忘记开 long long 和取模哦。整个程序的时间复杂度是 O ( n + m )，可以接受的。