算法笔记

数论

除法取模

  除法取模有一个((b)可以不是质数)公式: (adiv b mod p = (amod (b imes p))div b)

• 证明：
• (adiv b = k imes m + x, (x<m))
• 两边同乘(b)可得: (a = k imes m imes b + x imes b)
• 再对(a)取模: (a mod (m imes b) = x imes b)
• 两边同除(b)得: ((amod (m imes b))div b = x)

数根

九余数定理

计算组合数的时候别忘了c[0][0]，有时候会出错。

    for (int i = 0; i<maxn; ++i) c[i][0] = c[i][i] = 1;
    for (int i = 2; i<maxn; ++i)
        for (int j = 1; j<i; ++j)
            c[i][j] = (c[i-1][j]+c[i-1][j-1])%MOD;

图论

并查集

  路径压缩前的p[i]并不一定是最靠上的父节点，因为每次合并只是把b的父节点挂到了a的父节点下面。

语法相关

map自定义结构体做key

• 由于map是由红黑树实现的所以自定义结构体做key的时候需要重载'<'，而且为了避免冲突，需要用上结构体内的所有元素。

struct INFO {
    int x, y, z;
    INFO (int a, int b, int c) : x(a), y(b), z(c) {}
    bool operator < (const INFO & d) const {
        if (x==d.x) return y==d.y? z<d.z : y<d.y;
        return x<d.x;
    }
};