hdu4990 矩阵快速幂
快速 矩阵
2023-09-11 14:14:00 时间
题意:
给你一短代码,让你优化这个代码,代码如下
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
const int MAX=100000*2;
const int INF=1e9;
int main()
{
int n,m,ans,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
for(i=1;i<=n;i++)
{
if(i&1)ans=(ans*2+1)%m;
else ans=ans*2%m;
}
printf("%d\n",ans);
}
return 0;
},给出n,m让你输出ans <1<=n, m <= 1000000000>.
思路:
直接跑肯定TLE,这个题目我们可以推公式,如果推不出来可以直接打出来一些,然
后自己找公式,一般公式不会很复杂(复杂的自己一般不会呵呵)。
现在我们要求ai:
如果i是奇数
a[i] = a[i-1] * 2 + 1 = (a[i-2] * 2 + a[i-1]) + 1 = a[i-2]*2+a[i-1]+1
如果i是偶数
a[i] = a[i-1] * 2 = (a[i-2] * 2 + 1) + a[i-1] = a[i-2]*2+a[i-1]+1
两个公式一样,那么可以作为通式,然后就构造矩阵,之后跑快速幂就行了,矩阵也很好构
造,我构造下:
a1 a2 1 0 2 0 a2 a3 1
* 1 1 0
给你一短代码,让你优化这个代码,代码如下
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
const int MAX=100000*2;
const int INF=1e9;
int main()
{
int n,m,ans,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
for(i=1;i<=n;i++)
{
if(i&1)ans=(ans*2+1)%m;
else ans=ans*2%m;
}
printf("%d\n",ans);
}
return 0;
},给出n,m让你输出ans <1<=n, m <= 1000000000>.
思路:
直接跑肯定TLE,这个题目我们可以推公式,如果推不出来可以直接打出来一些,然
后自己找公式,一般公式不会很复杂(复杂的自己一般不会呵呵)。
现在我们要求ai:
如果i是奇数
a[i] = a[i-1] * 2 + 1 = (a[i-2] * 2 + a[i-1]) + 1 = a[i-2]*2+a[i-1]+1
如果i是偶数
a[i] = a[i-1] * 2 = (a[i-2] * 2 + 1) + a[i-1] = a[i-2]*2+a[i-1]+1
两个公式一样,那么可以作为通式,然后就构造矩阵,之后跑快速幂就行了,矩阵也很好构
造,我构造下:
a1 a2 1 0 2 0 a2 a3 1
* 1 1 0
0 1 1
#include<stdio.h> #include<string.h> __int64 M; typedef struct { __int64 mat[5][5]; }A; A mat_mat(A a ,A b) { A c; memset(c.mat ,0 ,sizeof(c.mat)); for(int k = 1 ;k <= 3 ;k ++) for(int i = 1 ;i <= 3 ;i ++) { if(a.mat[i][k]) for(int j = 1 ;j <= 3 ;j ++) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j])%M; } return c; } A quick_mat(A a ,int b) { A c; memset(c.mat ,0 ,sizeof(c.mat)); c.mat[1][1] = c.mat[2][2] = c.mat[3][3] = 1; while(b) { if(b&1) c = mat_mat(c ,a); a = mat_mat(a ,a); b >>= 1; } return c; } int main () { A a; int n ,i; while(~scanf("%d %d" ,&n ,&M)) { a.mat[1][1] = a.mat[1][3] = a.mat[2][3] = a.mat[3][1] = 0; a.mat[2][1] = a.mat[2][2] = a.mat[3][2] = a.mat[3][3] = 1; a.mat[1][2] = 2; if(n == 1) { printf("%d\n" ,1 % M); continue; } a = quick_mat(a ,n-1); __int64 Ans = 1 * a.mat[1][1] + 2 * a.mat[2][1] + 1 * a.mat[3][1]; printf("%I64d\n" ,Ans % M); } return 0; }
相关文章
- 【华为云技术分享】快速理解spark-on-k8s中的external-shuffle-service
- ECS 选款利器!PTS助您快速上云!
- Ubuntu 下用命令行快速打开html,mp3等文件
- 一个快速找到Spring框架是在哪里找到XML配置文件并解析Beans定义的小技巧
- 【图灵杯 F】一道简单的递推题(矩阵快速幂,乘法模板)
- 熬夜再战Android从青铜到王者-UI组件快速搭建App界面【建议收藏】
- Hadoop快速入门——第二章、分布式集群(第三节、HDFS Shell的常用命令)
- VS Code摸鱼神器,让你快速开发AI模型
- 寻找右区间-c语言快速排序加二分查找
- 利用矩阵快速幂转换的题目
- 矩阵快速幂在ACM中的应用
- vue-tour快速入门:VUE项目中如何使用vue-tour新手引导指引插件?怎样使用?包含具体实例
- Vitepress快速搭设博客&项目文档
- 基于在线优化的快速模型预测控制仿真Fast_MPC(Matlab代码实现)