BZOJ 2326: [HNOI2011]数学作业(矩阵乘法)
2024-09-03 10:04:33
解题思路
NOIp前看到的一道题,当时想了很久没想出来,NOIp后拿出来看竟然想出来了。注意到有递推\(f[i]=f[i-1]*poww[i]+i\),\(f[i]\)表示\(1-i\)连接起来组成的数字,\(poww[i]\)表示\(10\)的\(i\)的位数次幂,发现这个可以用矩阵快速幂优化,\([f[i],i+1,1]\),转移到\([f[i+1],i+2,1]\),要做\(n\)的位数次快速幂,每次修改一下转移矩阵中\(poww\)的值就行了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
typedef long long LL;
LL n,ans,poww[20]={1};
int MOD,wei;
struct Matrix{
LL a[4][4];
void clear(){memset(a,0,sizeof(a));}
friend Matrix operator*(const Matrix A,const Matrix B){
Matrix ret;ret.clear();
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
(ret.a[i][j]+=(LL)A.a[i][k]*B.a[k][j]%MOD)%=MOD;
return ret;
}
}pre,A;
Matrix fast_pow(Matrix x,LL y){
Matrix ret;ret.clear();ret.a[1][1]=ret.a[2][2]=ret.a[3][3]=1;
for(;y;y>>=1){
if(y&1) ret=ret*x;
x=x*x;
}
return ret;
}
signed main(){
scanf("%lld%lld",&n,&MOD);LL nn=n;
while(n) n/=10,wei++;
for(int i=1;i<=18;i++) poww[i]=poww[i-1]*10;
A.a[2][1]=A.a[2][2]=A.a[3][2]=A.a[3][3]=1;pre.a[1][2]=pre.a[1][3]=1;
for(int i=1;i<wei;i++) {
A.a[1][1]=poww[i]%MOD;
pre=pre*fast_pow(A,poww[i]-poww[i-1]);
}A.a[1][1]=poww[wei]%MOD;
pre=pre*fast_pow(A,nn-poww[wei-1]+1);
printf("%lld\n",pre.a[1][1]);
return 0;
}
最新文章
- 设计模式之接口隔离原则(ISP)
- .net之工作流工程展示及代码分享(一)工作流表单
- 让 innerHTML 进来的 script 代码跑起来
- C中不安全函数
- Crashing Robots 分类: POJ 2015-06-29 11:44 10人阅读 评论(0) 收藏
- [C#]Linq To Xml 介绍- 转
- UVA 1659 Help Little Laura 帮助小劳拉 (最小费用流,最小循环流)
- Ubuntu----1
- HTML5 canvas文本属性与方法
- SwfUpload及imgareaselect使用方法
- QT-Demo-Colck-01
- 如何理解java的引用传递
- caffe cifar10试跑问题总结
- 编译安装dropbear
- 【转】搭建spark环境 单机版
- python_str的应用
- 安装VUE Cli3 框架方法
- mssql sqlserver 获取指定汉字的笔画数的方法分享
- HDFS 开发中的文件配置优先级
- WebForm内置对象:Application和ViewState、Repeater的Command用法
热门文章
- hdu 5885 XM Reserves (FFT建模)
- [NOIP模拟26]题解
- MYSQL的SQL_CALC_FOUND_ROWS 和count(*)
- CenterOS 设置静态IP
- sql find_in_set在oracle下的解决方案
- ubuntu 18.04 自启动
- UVA 212 Use of Hospital Facilities
- Rust <;10>;:宏导出、导入
- Apache 2.4.12 64位+Tomcat-8.0.32-windows-x64负载集群方案
- Java实验报告(三)&;第五周课程总结