题目
给定 \(p = a + b\) 和 \(q = ab\) 和 \(n\)，求 \(a ^ n + b ^ n\)。
$0\le n\lt 2^{63} $
分析
大水题。
先考虑 \(n\) 较小的情况，可以很容易的想到递推：
\[\begin{array}{}
\text{令} F(i) & = a ^ n + b ^ n \\
& = (a + b)(a ^ {n - 1} + b ^ {n - 1}) - (ab ^ {n - 1} + a^{n - 1}b) \\
& = (a + b)(a ^ {n - 1} + b ^ {n - 1}) - ab(a ^ {n - 2} + b ^ {n - 2}) \\
& = p \times F(i - 1) - q \times F(i - 2)
\end{array}
\]
\text{令} F(i) & = a ^ n + b ^ n \\
& = (a + b)(a ^ {n - 1} + b ^ {n - 1}) - (ab ^ {n - 1} + a^{n - 1}b) \\
& = (a + b)(a ^ {n - 1} + b ^ {n - 1}) - ab(a ^ {n - 2} + b ^ {n - 2}) \\
& = p \times F(i - 1) - q \times F(i - 2)
\end{array}
\]
然后发现这个递推式可以用矩阵优化：
\[\left[\begin{matrix}
p & - q \\
1 & 0
\end{matrix}\right]
\times
\left[\begin{matrix}
F[i] \\
F[i - 1]
\end{matrix}\right] =
\left[\begin{matrix}
F[i] \times p & + & F[i - 1]\times (-q) \\
F[i] \times 1 & + & F[i - 1]\times 0
\end{matrix}\right] =
\left[\begin{matrix}
F[i + 1] \\
F[i]
\end{matrix}\right]
\]
p & - q \\
1 & 0
\end{matrix}\right]
\times
\left[\begin{matrix}
F[i] \\
F[i - 1]
\end{matrix}\right] =
\left[\begin{matrix}
F[i] \times p & + & F[i - 1]\times (-q) \\
F[i] \times 1 & + & F[i - 1]\times 0
\end{matrix}\right] =
\left[\begin{matrix}
F[i + 1] \\
F[i]
\end{matrix}\right]
\]
即：
\[\left[\begin{matrix}
p & - q \\
1 & 0
\end{matrix}\right]^n
\times
\left[\begin{matrix}
F[1] \\
F[0]
\end{matrix}\right] =
\left[\begin{matrix}
F[n + 1] \\
F[n]
\end{matrix}\right]
\]
p & - q \\
1 & 0
\end{matrix}\right]^n
\times
\left[\begin{matrix}
F[1] \\
F[0]
\end{matrix}\right] =
\left[\begin{matrix}
F[n + 1] \\
F[n]
\end{matrix}\right]
\]
显然，\(F[1] = p,\ F[0] = 2\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10;
struct matrix {
ll a[MAXN][MAXN]; int rowSize, lineSize;
matrix(int x, int y) {
rowSize = x; lineSize = y;
}
ll *operator [](const unsigned &i) {return a[i];}
matrix operator *(matrix y) {
matrix ans(rowSize, y.lineSize);
for(int i = 0; i < ans.rowSize; i++)
for(int j = 0; j < ans.lineSize; j++) {
ans[i][j] = 0;
for(int k = 0; k < lineSize; k++)
ans[i][j] += a[i][k] * y[k][j];
}
return ans;
}
} u(2, 2);
matrix qPow(matrix x, ll b) {
matrix ans = u, base = x;
while(b) {
if(b & 1)
ans = ans * base;
base = base * base;
b >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
u[0][0] = 1; u[0][1] = 0;
u[1][0] = 0; u[1][1] = 1;
ll p, q, n;
while(scanf("%lld%lld%lld", &p, &q, &n) == 3) {
matrix a(2, 2), b(2, 2), st(2, 1);
a[0][0] = p; a[0][1] = -q;
a[1][0] = 1; a[1][1] = 0;
st[0][0] = p; st[1][0] = 2;
b = qPow(a, n) * st;
printf("%lld\n", b[1][0]);
}
return 0;
}
UVA10655 Contemplation! Algebra