#矩阵乘法#SSL 1529 斐波那契数列
#题目
求斐波那契数列的第n项%10000
#分析
可以用矩阵乘法加速递推。
【#矩阵乘法#SSL 1529 斐波那契数列】#代码
#include
#define mod 10000
using namespace std;
int n,f[2]={0,1},a[2][2]={{0,1},{1,1}};
void mul(int f[2],int a[2][2]){
int c[2]={0,0};
for (int j=0;
j<2;
j++)
for (int k=0;
k<2;
k++)
c[j]=(c[j]+f[k]*a[k][j])%mod;
f[0]=c[0];
f[1]=c[1];
}
void mulself(int a[2][2]){
int c[2][2]={{0,0},{0,0}};
for (int i=0;
i<2;
i++)
for (int j=0;
j<2;
j++)
for (int k=0;
k<2;
k++)
c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
a[0][0]=c[0][0];
a[0][1]=c[0][1];
a[1][0]=c[1][0];
a[1][1]=c[1][1];
}
int main(){
scanf("%d",&n);
while (n)
{
if (n&1) mul(f,a);
mulself(a);
n>>=1;
}
printf("%d",f[0]);
}
推荐阅读
- #矩阵中的鞍点
- 混淆矩阵画图
- 蒙哥马利乘法原理
- 【数组题】给定一个二进制矩阵|【数组题】给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
- 长乘法|长乘法 --- 多位数乘两位数（乙未三下带入）
- CapsNet|CapsNet 胶囊网络理解
- 矩阵堆栈操作
- 对矩阵的操作2
- 矩阵函数的常见求法
- 给定一个|给定一个 n × n 的二维矩阵表示一个图像, 将图像顺时针旋转 90 度js实现