鹏鹏的旧OI博客

高二及以前的哦,只剩文字了,图片、附件等都没了



一些大概没有什么卵用的数学知识

拓展欧几里得

int ex_gcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    int t=ex_gcd(b,a%b,y,x);
    y-=a/b*x;return t;
}

中国剩余定理

//

Pólya计数法

$$ L = \frac{1}{|G|} \sum_{i=1}^{s} D(a_{i}) = \frac{1}{|G|} \sum_{i=1}^{s} m^{c(a_{i})} $$
L表示本质不同的方案数,G表示置换群,|G|表示置换群的阶数,D(a)表示在置换a下不变的元素的个数,m表示颜色种数,c(a)表示置换a的循环节数。


逆元

在mod p意义下,如果要求t/a,可以先求得a的逆元,记为\( a^{-1} \),于是t/a就可以变成计算\(
t × a^{-1} \)。直接计算逆元的代码就是个拓展欧几里得。也可以递推得到。