网站建设亿金手指花总14,建筑工程承包网址大全,南沙建设局网站,阿里巴巴官网网站【题目来源】https://www.acwing.com/problem/content/1305/http://poj.org/problem?id3070【题目描述】 大家都知道 数列吧#xff0c;。现在问题很简单#xff0c;输入 和 #xff0c;求 的前 项和 。【输入格式】 共一行#xff0c;包含两个整数 和 。【输出格式】…【题目来源】https://www.acwing.com/problem/content/1305/http://poj.org/problem?id3070【题目描述】 大家都知道 数列吧。现在问题很简单输入 和 求 的前 项和 。【输入格式】 共一行包含两个整数 和 。【输出格式】 输出前 项和 的值。【数据范围】【输入样例】 5 1000【输出样例】 12【算法分析】 ★ 矩阵快速幂加速递推 1已知 数列递推式为 但当 极大时会超时。 故基于“矩阵快速幂加速递推”的思路改写数列递推式 为 改写后的递推式对应的 LaTex 代码为
[F_n \quad F_{n-1}][F_{n-1} \quad F_{n-2}]
\begin{bmatrix}
1 1\\
1 0
\end{bmatrix}
[F_{n-2} \quad F_{n-3}]
\begin{bmatrix}
1 1\\
1 0
\end{bmatrix}
\begin{bmatrix}
1 1\\
1 0
\end{bmatrix}
\cdots [F_1,F_0]
\begin{bmatrix}
1 1\\
1 0
\end{bmatrix}^{n-1}
2若令 则有 。 据此公式可知首先求出 然后用 左乘便可得到 而 的第一个元素即为 。注意标红的公式技巧在于使用了 LaTex 命令 \textcolor{red} {公式}
\textcolor{red} {X_nX_1\times A^{n-1}}
★ 矩阵快速幂模板https://blog.csdn.net/hnjzsyjyj/ar左乘ticle/details/143227091【算法代码】
#includebits/stdc.h
using namespace std;typedef long long LL;
LL A[2][2] {{1,1},{1,0}
};
LL ans[2] {1,0}; //save answerint n,m;//Column matrix A * matrix B
void mul1(LL A[], LL B[][2]) {LL t[2] {0};for(int i0; i2; i)for(int j0; j2; j)t[i]A[j]*B[i][j]%m;for(int i0; i2; i)A[i]t[i]%m;
}//matrix A * matrix B
void mul2(LL A[][2], LL B[][2]) {LL t[2][2] {0};for(int i0; i2; i)for(int j0; j2; j)for(int k0; k2; k)t[i][j]A[i][k]*B[k][j]%m;for(int i0; i2; i)for(int j0; j2; j)A[i][j]t[i][j]%m;
}int main() {scanf(%d%d,n,m);n2; //get f[n2]while(n) { //fastPowif(n 1) mul1(ans,A);mul2(A,A);n1;}printf(%lld\n, ans[1]-1); //ans[1] is f[n2]return 0;
}/*
in:
5 1000out:
12
*/
【参考文献】https://www.acwing.com/blog/content/25/https://blog.csdn.net/hnjzsyjyj/article/details/143227091https://www.cnblogs.com/yijiull/p/6641422.htmlhttps://www.acwing.com/solution/content/15121/
