简介
快速幂是能快速计算一个幂的方案,他可以作用于所有满足结合律、封闭性的二元运算,即半群
定义
不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时,不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$
快速幂核心思想
在半群中,只要$k=u+v$一定有$x^k=x^u\circ x^v$.
所以我们可以把k看作一个二进制数,把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$
这里最多分解为$\log_2(k)$个元素,而且每个元素可以由前k个元素获取,所以只需要进行$log_2(k)$次二元计算即可的到最终答案。
代码
| T qpow(T a,int k){ T res = getE(); while(k){ if(k&1){ res = binaryOp(res,a); } a = binaryOp(a,a); k>>=1; } return res; }
|
加法模群快速幂
在加法模群中,getE()
定义为0,因为任何数加上0得到自身。binaryOp
为二元运算$binaryOp(x,y)=(x+y)\mod p$。
乘法模群快速幂
在乘法模群中,getE()
定义为1,因为任何数乘以1得到自身。binaryOp
为二元运算$binaryOp(x,y)=(x\cdot y)\mod p$。
矩阵乘法模群快速幂
在矩阵乘法模群中,getE()
定义为矩阵的单位元,即对角线全为1的对角矩阵。binaryOp
为普通矩阵模乘。
无理数乘法快速幂
很多时候我们需要用到无理数,即设一个无理数$y=\sqrt{(c_1)}\cdot x_1+x_2$, 其中$x$为变量,$c$均为常量,一个无理数可以被唯一标识为一个二元组$(x_1,x_2)$,
这时候单位元是getE()
=$(0,1)$, binaryOp
为普通无理数乘法。
置换群快速幂
在置换中,单位元为$h=\begin{pmatrix}
1 & 2 & 3 &… &n\
1 & 2 & 3 &… &n
\end{pmatrix}$ ,binaryOp
为普通置换乘法。
十进制快速幂
有的时候,给你的k是一个10进制大数,由于我们朴素的快速幂需要使用二进制的k(后面有移位),所以会遇到一些麻烦。
当然,最简单的就是直接分解为十进制乘法。
$x^k=x^{10^{p_1}}\circ x^{10^{p_2}}\circ x^{10^{p_3}}\circ \circ \circ x^{10^{p_n}}$
道理都是一样的。这里最多分解出$\log^{10}(k)$个元素,每个$x^{10^1}$可以从前一项直接运算推导。最多进行$\log^{10}(k)$次计算
代码
矩阵快速幂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| typedef long long ll; const int LEN=3;
void sarray_cpy(int a[][LEN],int b[][LEN],int n){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++) b[i][j]=a[i][j]; } }
void sarray_mul(int a[][LEN],int b[][LEN],int ret[][LEN],int n,int mod){ static int c[LEN][LEN]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ c[i][j]=0; for(int k=0;k<n;k++){ c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod; } } } sarray_cpy(c,ret,n); }
void sarray_qpow(int aa[][LEN],ll b,int ret[][LEN],int n,int mod){ static int a[LEN][LEN]; sarray_cpy(aa,a,n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++) ret[i][j]=0; ret[i][i]=1; } while(b){ if(b&1) sarray_mul(ret,a,ret,n,mod); sarray_mul(a,a,a,n,mod); b>>=1; } }
void sarray_add(int a[][LEN],int b[][LEN],int c[][LEN],int n,int mod){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ c[i][j]=(a[i][j]+b[i][j])%mod; } } }
void sarray_sum(int a[][LEN],ll b,int ret[][LEN],int n,int mod){ static int tmp[LEN][LEN]; if(b==0) sarray_qpow(a,b,ret,n,mod); else{ ll mid=(b-1)>>1; sarray_sum(a,mid,ret,n,mod); sarray_qpow(a,mid+1,tmp,n,mod); for(int i=0;i<n;i++) tmp[i][i]=(tmp[i][i]+1)%mod; sarray_mul(ret,tmp,ret,n,mod); if((b&1)==0) { sarray_mul(ret,a,ret,n,mod); for(int i=0;i<n;i++) ret[i][i]=(ret[i][i]+1)%mod; } } }
int trans[LEN][LEN]={ 1,1,1, 1,0,0, 0,1,0 };
|
十进制快速幂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include<bits/stdc++.h> using namespace std;
void mul(const int a[2][2],const int b[2][2],int c[2][2],int mod){ int res[2][2]={}; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ for(int k=0;k<2;k++) res[i][j]=(res[i][j]+1ll*a[i][k]*b[k][j])%mod; } } memcpy(c,res,sizeof(res)); }
void qpow(const int aa[2][2],int b,int c[2][2],int mod){ int a[2][2]; memcpy(a,aa,sizeof(a)); int res[2][2]={ 1,0, 0,1 }; while(b){ if(b&1) mul(res,a,res,mod); mul(a,a,a,mod); b>>=1; } memcpy(c,res,sizeof(res)); }
void qpow(const int aa[2][2],char*b,int ed,int c[2][2],int mod){ int a[2][2]; memcpy(a,aa,sizeof(a)); int res[2][2]={ 1,0, 0,1 }; while(ed>=0){ int t[2][2]; qpow(a,b[ed]-'0',t,mod); mul(res,t,res,mod); qpow(a,10,a,mod); ed--; } memcpy(c,res,sizeof(res)); }
const int maxn=1e6+6; char s[maxn]; int main(){ int x0,x1,a,b,mod; scanf("%d%d%d%d%s%d",&x0,&x1,&a,&b,s,&mod); int trans[2][2]={ a,b, 1,0 }; int ans[2][2]={ x1,0, x0,0 }; int trans2[2][2]; qpow(trans,s,int(strlen(s))-1,trans2,mod); mul(trans2,ans,ans,mod); cout<<ans[1][0]<<endl; }
|