BZOJ 2326: [HNOI2011]数学作业( 矩阵快速幂 )
2024-08-26 14:00:00
BZOJ先剧透了是矩阵乘法...这道题显然可以f(x) = f(x-1)*10t+x ,其中t表示x有多少位。
这个递推式可以变成这样的矩阵...(不会用公式编辑器...), 我们把位数相同的一起处理, 那么10^t就可以确定,加上快速幂就行了
------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef int matrix[3][3];
ll N;
int MOD;
matrix mat, Q, tmp;
void Mul(matrix &a, matrix &b) {
memset(tmp, 0, sizeof tmp);
for(int i = 0; i < 3; i++)
for(int k = 0; k < 3; k++)
for(int j = 0; j < 3; j++)
if((tmp[i][j] += ll(a[i][k]) * b[k][j] % MOD) >= MOD)
tmp[i][j] -= MOD;
memcpy(a, tmp, sizeof a);
}
void Power(matrix &a, matrix &b, ll k) {
for(; k; k >>= 1, Mul(b, b))
if(k & 1) Mul(a, b);
}
void Init_matrix() {
memset(mat, 0, sizeof mat);
mat[0][1] = mat[0][2] = mat[1][1] = mat[1][2] = mat[2][2] = 1;
memset(Q, 0, sizeof Q);
for(int i = 0; i < 3; i++)
Q[i][i] = 1;
}
int main() {
scanf("%lld%d", &N, &MOD);
int len = 0, B = 0, C = 0;
ll p = 1;
for(ll t = N; t; t /= 10, len++);
for(int i = 1; i < len; i++) {
Init_matrix();
mat[0][0] = (p = p * 10) % MOD;
Power(Q, mat, p - p / 10);
B = (ll(B) * Q[0][0] % MOD + ll(C) * Q[0][1] % MOD + Q[0][2]) % MOD;
C = ((p % MOD) - 1 + MOD) % MOD;
}
Init_matrix();
mat[0][0] = p * 10 % MOD;
Power(Q, mat, N - p + 1);
B = (ll(B) * Q[0][0] % MOD + ll(C) * Q[0][1] % MOD + Q[0][2]) % MOD;
printf("%d\n", B);
return 0;
}
------------------------------------------------------------------------------------
2326: [HNOI2011]数学作业
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1452 Solved: 841
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
HINT
Source
最新文章
- 【UOJ #14】【UER #1】DZY Loves Graph
- jstl core 库 之 out set remove
- CSS中position小解
- 淘宝网触屏版 - 学习笔记(1 - 关于meta)
- 微信小程序 开发 微信开发者工具 快捷键
- Xshell4注册码,Xftp注册码
- PHP获取不了React Native Fecth参数的解决办法代码是怎样?
- asp.net中virtual和abstract的区别分析
- 面试题收集——Java基础部分(一)
- ExtJs 第二章,Ext.form.Basic表单操作
- 日期 bootsrtap-datatimepicker and bootstrap-datepicker 控件支持中文
- 原生javascript实现老.虎机抽奖点名demo源码思路解析
- java.io.IOException: Invalid header signature; read 0xE011BDBFEFBDBFEF, expected 0xE11AB1A1E011CFD0
- 洛谷P3375 - 【模板】KMP字符串匹配
- thinkphp5.0引入类
- 步步为营102-Css样式加个版本
- virtual和abstract的区别
- Google Optimization Tools实现加工车间任务规划【Python版】
- 替换NSUserDefaults的方案
- NOI 4978 宠物小精灵之收服(二维背包)
热门文章
- winds引导配置数据文件包含的os项目无效
- Android Afinal框架学习(二) FinalActivity 一个IOC框架
- 应用程序正常初始化(0xc015002)失败解决方法
- C# SQL文件执行器的功能实现
- 大型票务系统中username和password的安全性问题
- Java中Lambda表达式的使用
- 获取 web容器中的bean
- 使用mybatis查询数据,按特定顺序排序
- The error indicates that IIS is in 32 bit mode, while this application is a 64 b it application and thus not compatible.
- mobile&;nbsp;web&;nbsp;手机开发