逆元求解
费马小定理
假如a是一个整数,b是一个素数,\(gcd(a,p)=1\),则
\(a^{p-1}\equiv1(mod(p))\) 应用:- 降次:\(a^bmod(p)=a^{(b)mod (p)}mod(p)\)
质数逆元:\(\frac{1}{a}mod (p)=a^(p-2)mod(p)\)
欧拉定理
若\(n,a\)为正整数,且\(n,a\)互质,则
\(a^{\phi(n)}\equiv 1(mod(n))\) 费马小定理是欧拉定理的特殊情况,因为\(n\)为素数时,\(\phi(n)=n-1\)。 拓欧降次:- 当\(n>1\)时,\(a^b\%n=a^{b\%\phi(n)}\%n\)
- 当\(b\leq\phi(n)\)时,暴算
- 当\(b>\phi(n)\)时,\(a^b\%n=a^{b\%\phi(n)}\%n\) 拓欧解方程
求解\(a\equiv 1(mod(q)),x>0\)
则x解集为\(\phi(q)\)的约数与倍数。实践
给定\(a,p(p>1),gcd(a,p)=1\),求\(a\)在模\(p\)意义下的逆元。
- 用Exgcd解方程\(ax\equiv 1(mod(p))\) 即\(ax+by=1\)
int exgcd(int a,int b,int &d,int &x,int &y){ if(!b) x=1,y=0,d=a; else exgcd(b,a%b,d,y,x),y-=x*(a/b);}{ re int a; exgcd(i,p,g,x,y); while(x<0) x+=p; printf("%d\n",x);}
- 利用欧拉定理\(a^{\phi(n)}\equiv1(mod(n))\) 有式\(a^{-1}\equiv a^{\phi(n)-1}(mod(n))\)
- n为质数时,费马小定理\(a^{-1}\equiv a^{n-2}(mod(n))\)
线性求解
\(inv[i]=(p-p/i)*inv[p\%i]\)矩阵乘法
struct matrix{ int a[100][100]; matrix() { memset(a,0,sizeof(a)); } int * operator [](int x) { return a[x]; } matrix operator *(matrix b) { matrix c; for(int i=0;i
高斯消元
[专题总结][1]
组合数学
不可重组合数学(留坑)
- \(C^n_m\)表示在\(m\)中选\(n\)个的方案数。(把\(m\)个无区别物品放到\(n\)个有区别篮子的方案数)\(C^m_n=\frac{n!}{m!(n-m)!}\)\(C^m_n=C_{n-1}^{m-1}+C^m_{n-1}\)\(C^k_n=C^{n-k}_n\)\(C^{k+1}_n=C^k_n*\frac{n-k}{k+1}\)\[(a+b)^n=\sum^n_{k=0}C_n^k a^{n-k} b^k\]
- \(P^n_m\)表示在\(m\)中选\(n\)个的排列数。(把\(m\)个有区别物品放到\(n\)个有区别篮子的方案数)\(P_m^n=C_m^n*n!\)
- \(S^n_m\)表示斯特林数。(把\(m\)个有区别物品放到\(n\)个无区别篮子,且篮子不空的方案数)\(S_m^n=S_m^{n-1}*m+S_{m-1}^{n-1}\)\(S_m^n=0(m>n)\)
可重组合数学
可重排列
有\(k\)个元素,其中第\(i\)个元素有\(n_i\)个,求全排列数。
\(P'=\frac{(\sum_{i=1}^k n_i)!}{n_i!n_2!...n_k!}\) 即先全排列,然后给每个元素编号。可重组合
有\(k\)个元素,每个元素可选无穷多个,一共选\(k\)个,求方案数。
\(C'=C_{k-n+1}^{n-1}=C_{k-n+1}^k\) 假如第\(i\)个元素选\(x_i\)个,那么原问题变为\(x_1+x_2+...+x_n=k\)。 令\(y_i=x_i+1\),那么\(y_1+y_2+y_3+...+y_n=k+n\) 此时\(y>0\),即每个元素都要选。所以等于在\(k+n\)个元素(\(k+n-1\)个空位)间放\(n-1\)个隔板。卡特兰数
前几个数:\(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 1767263190\)
- 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
- n个节点构成的二叉树,共有多少种情形?
- 求一个凸多边形区域划分成三角形区域的方法数?
- 在圆上选择2n个点,将这些点成对链接起来使得所得到的n条线段不相交,一共有多少种方法?
- n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数.
- n层的阶梯切割为n个矩形的切法数。 [1]: