[T]快速幂

快速幂"/>

[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(log2​n)

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∑n​ai,k​bk,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;
}

或者你也可以不用重载，直接用函数达到相同效果