HDU4990 Reading comprehension
发布日期:2021-06-29 05:37:43
浏览次数:3
分类:技术文章
本文共 1615 字,大约阅读时间需要 5 分钟。
Reading comprehension
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1895 Accepted Submission(s): 753
Problem Description
Read the program below carefully then answer the question.
#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; }
Input
Multi test cases,each line will contain two integers n and m. Process to end of file.
[Technical Specification] 1<=n, m <= 1000000000
Output
For each case,output an integer,represents the output of above program.
Sample Input
1 10
3 100
Sample Output
1
5
分析:题目给的程序的意思就是给了一个递推式,但是在奇数和偶数的时候递推式不同。写几个后可以发现规律,找出一个统一的递推式。1,2,5,10,21,42,85......其中的规律是f(n) = f(n-1) + f(n-2)*2 + 1。这样的话可以用矩阵快速幂来计算。如下图:
代码:
#include#include #include #include using namespace std;typedef long long ll;long long n, m;void f(ll a[][3], ll b[][3]){ ll c[3][3]; for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ c[i][j] = 0; for(int k = 0; k < 3; k++){ c[i][j] += a[i][k]*b[k][j] % m; } c[i][j] %= m; } } for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) a[i][j] = c[i][j];}int main(){ while(cin>>n>>m){ ll a[3][3] = {1,1,0, 2,0,0, 1,0,1}; ll b[3][3] = {0,0,1, 0,0,0, 0,0,0}; while(n){ if(n&1) f(b, a); f(a, a); n >>= 1; } cout< <
转载地址:https://blog.csdn.net/zhj_fly/article/details/75339384 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月17日 00时30分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2021-07-02
各种滤波器合集!
2021-07-02
国产CPU深度研究报告(干货,110页)
2021-07-02
在电路中,耦合是什么?有哪些方式?
2021-07-02
变局之际,聊聊物联网的过去、现在和未来
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
单片机6年想转嵌入式Linux ,不知如何下手?
2019-04-29
拆解 | 某平台19元的儿童电话手表,究竟怎么做到的?
2019-04-29
五一好礼70份免费送:示波器、开发板、焊台等!
2019-04-29
2纳米芯片问世!芯片性能要起飞?!
2019-04-29
ARM Cortex系列那么多处理器,该怎么区分?
2019-04-29
知乎:学计算机的女生都怎么样了?
2019-04-29