快速幂"/>
[T]快速幂
前置
取模运算 % \% %,就是取余
快速幂
快速运算 a k a^k ak,尤其 k k k较大时
从原先 O ( k ) O(k) O(k)优化至 O ( l o g 2 n ) O(log_2n) O(log2n)
ll quick_mul(ll a,ll k)
{ll ans=1;while(k){if(k&1)ans=ans*a%mod;a=a*a%mod;k>>=1;}return ans;
}//这里常用一个函数来写,因为会经常调用
模板题
EX
乘法逆元
板子题
(费马小定理)大部分情况下 a − 1 ≡ a p − 2 ( m o d p ) a^{-1}\equiv a^{p-2}(mod\ p) a−1≡ap−2(mod p)
至于为什么是大部分情况,一般不考虑,除非出题人脑子有坑
推销:我古老的博客和另一份古老的博客
模数p一般为998244353(一个大质数)
番外
矩阵快速幂
前置矩阵处理(学会这个你就会线性代数了,或者线性代数学会了就会这part)
矩阵乘法
c i , j = ∑ k = 1 n a i , k b k , j c_{i,j}=\sum_{k=1}^n a_{i,k}b_{k,j} ci,j=k=1∑nai,kbk,j
重载
将原本有的符号重新定义
struct sq{long long num[102][102];sq(){memset(num,0,sizeof(num));}
};
sq operator *(sq a,sq b)//重新定义一个对于结构体sq矩阵的乘法
//基本格式:返回类型 operator 符号(所需参数)
{sq ans;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;}}return ans;
}
//于是乎,正常的快速幂板子就可以用了
sq quick_mul(sq a,ll k)
{sq ans=1;while(k){if(k&1)ans=ans*a;a=a*a;k>>=1;}return ans;
}
或者你也可以不用重载,直接用函数达到相同效果
更多推荐
[T]快速幂
发布评论