数论
HCl_Violet
·
·
个人记录
乘法逆元
有五种求法：
- 枚举法(单个)
- 利用费马小定理（单个）
$∵a^{p-1}≡1~(mod)~p
∴a*a^{p-2}≡1~(mod~p)
∴x=a^{p-2}~mod~p
寻找 a*x≡1~(mod~p)的解其实就相当于寻找方程 a*x+p*y=1 的解。
再一看： a,p 一定互质，这不就是扩展欧几里得算法的标准形式吗！
不会
设k'为k的逆元
可推得：
k'=-(p/k)*(p~mod~k)'~mod ~p
具体证明请点击标题 （反正我不会）。
Miller-Rabin和Pollard-Rho算法
BLOG_2
Miller-Rabin：检验是否为质数；
Pollard-Rho:大整数分解质因数；
同理，具体讲解，请点击标题 （我依然不会）。
Lucas定理：
$Lucas(n,m,p)=$ $cm(n~mod~p,m ~mod~p)$ $×Lucas(n/p~,m/p,~p)
Lucas(x,0,p)=1$ , $cm(a$,$b)=$ $(a!/(a-b)!)^{(p-2)}~~mod~~p
然后这道求组合数的题，就做出来了。
(还不会？那就背过！)
卷积式
对于组合数C^m_n，我们任选一个正整数p≤n，将n个元素分成p个和n-p个两份。假设我们从前p个元素中选i个放进筐，则需要将从后n-p个元素种选出剩下的m-i个。考虑到i所有可能的取值，我们能够得到这样的式子
C^m_n=Σ^m_{i=0}C^i_pC^{m-i}_{n-p}
这玩意也叫
范德蒙德卷积式
```cpp
void work(int n){
if(n==1)return;
if(!(n&1)){
work(n>>1);
for(int i=0;i<=m;i++){
g[i]=0;
for(int j=0;j<=i;j++)
g[i]+=f[j]%q*f[i-j]%q;
g[i]%=q;
}
for(int i=0;i<=m;i++)
f[i]=g[i];
}
else{
work(n-1);
for(int i=1;i<=m;i++){
g[i]=f[i-1]%q+f[i]%q;
g[i]%=q;
}
for(int i=1;i<=m;i++)
f[i]=g[i];
}
}
```
~~这个码跑的挺慢的~~
## 矩阵：[可爱即是正义！](https://www.luogu.org/blog/shehuizhuyihao/post-zhen-sheng-fa)
- 矩阵加法：对应元素相加即可；
- 矩阵乘法：
$(A*B)_{i,j}=Σ^p_{k=1}A_{i,k}B_{k,j}
```cpp
for(int i = 0; i <= k; i++)
for(int t = 0; t <= k; t++)
for(int j = 0; j <= k; j++)
bj[i][j] = b[i][t] * f[t][j];
```
- 矩阵乘法满足结合律但不满足交换律
$~~~~~A(BC)=(AB)C
据此，我们可以得到矩阵的快速幂；
```cpp
void cal(){
for(int i=0;i<=k;i++){
g[i]=0;
for(int j=0;j<=k;j++){
g[i]=(g[i]+b[i][j]*f[j][0])%mod;
}
}
for(int i=0;i<=k;i++){
f[i][0]=g[i];
}
}
void beizeng(){
for(int i=0;i<=k;i++)
for(int o=0;o<=k;o++)
for(int j=0;j<=k;j++){
bj[i][j]=(bj[i][j]+b[i][o]*b[o][j])%mod;
}
for(int i=0;i<=k;i++){
for(int j=0;j<=k;j++){
b[i][j]=bj[i][j];
bj[i][j]=0;
}
}
}
int main()
{
//省略~~
cin>>n;
while(n){
if(n&1) cal();
beizeng();
n>>=1;
}
}
```