HDU 1757 矩阵快速幂加速递推
2024-10-01 09:06:31
题意:
已知:
当x<10时:f(x)=x
否则:f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + ……+ a9 * f(x-10);
求:f(x)%m的值。
思路:
矩阵快速幂加速递推。 嗯嗯
// by SiriusRen
#include <cstdio>
#include <cstring>
using namespace std;
int cases,k,ans,a[10][10],mod;
struct matrix{int a[10][10];void init(){memset(a,0,sizeof(a));}}first,cpy,td;
matrix mul(matrix &a,matrix &b,int x){
matrix temp;temp.init();
for(int i=0;i<10;i++)
for(int j=0;j<x;j++)
for(int k=0;k<10;k++)
temp.a[i][j]=(a.a[i][k]*b.a[k][j]+temp.a[i][j])%mod;
return temp;
}
int main(){
while(~scanf("%d%d",&k,&mod)){
cpy.init();first.init();
ans=0;
for(int i=0;i<10;i++)scanf("%d",&first.a[9][9-i]),cpy.a[9][9-i]=first.a[9][9-i];
for(int i=0;i<9;i++)first.a[i][i+1]=cpy.a[i][i+1]=1;
for(int i=0;i<10;i++)td.a[i][0]=i;
if(k<10)printf("%d\n",k%mod);
else{k-=10;
while(k){
if(k&1)first=mul(cpy,first,10);
cpy=mul(cpy,cpy,10);k>>=1;
}
first=mul(first,td,1);
printf("%d\n",first.a[9][0]);
}
}
}
最新文章
- poj1062 昂贵的聘礼
- ARP协议格式、ARP运行机制入门学习
- 猫都能学会的Unity3D Shader入门指南
- JS 跨域问题浅析及解决方法优缺点对比(转)
- inline和宏之间的区别
- Sql 解释
- (转)PHP获取今天、昨天、明天的日期
- windows和linux下获取当前程序路径以及cpu数
- PIE使用阴影后的背景透明方法
- mysql存入中文乱码问题
- 呵呵哒,LNMP下通过fread方式下载文件时,中文名称文件找不到文件
- python 特殊方法实例
- $(function(){})和window.onload的区别
- 后台返回excel文件流,js下载
- php快速定位当前调用的类的位置
- pandas绘图
- IP地址分类以及子网划分
- Go语言学习之3 流程控制、函数
- linux命令学习之:du
- 使用docusaurus 搭建开发&;&;api &;&; 博客站点