快速幂

人话

求\(a\)的\(n\)次方，其实就是根据二进制唯一分解定理给\(a^n\)拆成\(\log{n}\)个\(a^{2^i}\)，递推求出从\(a^0\)到\(a^{2^i}\)每个数，如果\(n\)的二进制第\(i\)位为1，则将答案乘上\(a^{2^i}\)

ll Qpow(ll a,ll b)
{
    //一开始a就是a的一次方
    ll ans=1;
    while(b) //只要还没乘完
    {
        if(b&1) ans=ans*a%p;//拆分过后这一位是1，所以乘上2的x次方
        a=a*a%p; //a变为a的二次方，四次方，八次方，十六次方....
        b=b>>1;  //非常好理解，这一位算完了，直接右移掉
    }
    return ans%p;
}

高精度加法

线性基

性质

我们设原集合为\(S\)，线性基集合为\(P\)
1.S中任意元素可以用P中的一些数异或和表示(表示方法唯一)
2.线性基任意数异或和不为0(与第一条括号内等价)

code