冪運算
冪運算\(a^b\)是\(b\)個\(a\)相乘的結果.
C++自帶的冪函式pow是最樸素的\(O(b)\)演算法,效率非常低,所以如果要用到大量冪運算,最好自己打一個快速冪.
快速冪
求\(a^b\%p\)的值.
- 當\(b=1\)時,回傳\(a%p\).
- 當\(2\mid b\)時,回傳\(pow(a,\frac{b}{2},p)^2%p\).
- 當\(2\nmid b\)時,回傳\(pow(a,\frac{b}{2},p)^2%p*a%p\).
時間復雜度為\(O(\log{b})\).
long long poww(long long a,long long b,long long p) {
if(b==1) return a%p;
long long t=1;
t=poww(a,b/2,p);
t=t*t%p;
if(b%2) t=t*a%p;
return t;
}
這樣寫也行
long long poww(long long a,long long b,long long p) {
long long ans=1;
while(b) {
if(b%2==1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
矩陣乘法
運算方法
矩陣加法,減法,矩陣乘常數這三種運算都很簡單,這里不贅述.
有兩個分別為\(n\times m\),\(m\times p\)的矩陣\(a,b\)相乘,結果是一個\(n\times p\)的矩陣\(c\).
\(c[i][j]=\sum\limits_{k=1}^{m}{a[i][k]*b[k][j]}\).
代碼用結構體實作.
struct mat {
long long (*x)[505]=new long long[505][505];//如果矩陣比較小就直接開陣列,太大就用指標.
/*mat() {
memset(x,0,sizeof(x));
}*/ //直接開陣列要初始化.
friend mat operator * (mat a,mat b) {//多載
mat c;
for(long long i=1; i<=n; i++) {
for(long long j=1; j<=m; j++) {
for(long long k=1; k<=p; k++) {
c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%MOD)%MOD;
}
}
}
return c;
}
};
時間復雜度為\(O(nmp)\)
常數優化
如果\(a[i][j]=0\),那么會浪費許多時間來計算\(a[i][j]\)與其他數的乘積.
只要改一下回圈嵌套的順序,并判斷\(a[i][j]\)是否等于\(0\),如果是就直接continue.
struct mat {
long long (*x)[505]=new long long[505][505];
friend mat operator * (mat a,mat b) {
mat c;
for(long long k=1; k<=p; k++) {
for(long long i=1; i<=n; i++) {
if(a.x[i][k]==0) continue;//優化
for(long long j=1; j<=m; j++) {
c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%MOD)%MOD;
}
}
}
return c;
}
};
矩陣快速冪
其實就是把快速冪中的數換成矩陣.
矩陣快速冪的應用
斐波那鍥數列 P1962
這是一個矩陣(\(f(n)\)表示斐波那鍥數列第\(n\)項)
\(\left\{
\begin{matrix}
f(n-1) \\
f(n-2)
\end{matrix}
\right\}\)
不難很難發現,只要讓它乘上矩陣
\(\left\{
\begin{matrix}
1 & 1 \\
1 & 0
\end{matrix}
\right\}\)
就能變成\(\left\{
\begin{matrix}
f(n) \\
f(n-1)
\end{matrix}
\right\}\)
所以如果要求\(f(n)\),只需算出\(\left\{
\begin{matrix}
f(n-1) \\
f(n-2)
\end{matrix}
\right\}
*
\left\{
\begin{matrix}
1 & 1 \\
1 & 0
\end{matrix}
\right\}^{n-1}\)
結果的第一行第一列就是\(f(n)\).
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71522.html
標籤：C++