对1000000007取模和0x3f3f3f3f

1. 结果可能很大的题目会要求对1000000007取模(1八个零7)，为什么？
最终我在柳神的博客下找到了答案

• 1000000007是一个质数（素数），对质数取余能最大程度避免冲突

• int32位的最大值为2147483647，1000000007同一个量级，足够大

• int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出

• 所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出

柳神说她猜的！https://www.liuchuo.net/archives/645

论述生动，内容充分，细节丰富，令人信服！反正我信了

2. 有些题解不是用Integer.MAX_VALUE而是0x3f3f3f，为什么？

Java提供了Integer.MAX_VALUE，Integer.MIN_VALUE，c++在climits头文件也有同样的符号定义，这两个的值通常是为了初始化比较值

1
2
3
4
5

int max = Integer.MIN_VALUE;
···
while(){
    max = Math.max(a, max);
}

Integer.MAX_VALUE值就是int的最大值，也就是0x7fffffff（7七个f），即2,147,483,647

有些题目不仅仅是要比较，还需要其他运算，如果进行了+1，那就会溢出成负数。因此有的acmer会采用0x3f3f3f3f，满足“无穷大加无穷大依然是无穷大”，这个设置非常精妙

• 0x3f3f3f3f足够大，十进制是10^9仍然和0x7fffffff在同样的数量级

• 0x3f3f3f3f+ 0x3f3f3f3f结果仍在32-bit int的表示范围之内，满足了“无穷大加无穷大还是无穷大”的需求

• 意想不到的额外好处：c++中通常会使用memset(a,0,sizeof(a))这样的代码来将数组清零，因为memset是按字节操作的因此非常高效，它能够对数组清零是因为0的每个字节都是0。但是当我们想将某个数组全部赋值为无穷大时就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦），现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。至于Java尚不清楚Arrays.fill(arr,0);仍然是循环