hdu 4990 Reading comprehension(等比数列法)
2024-09-29 22:44:46
思路:曾经有一个矩阵乘法的做法请戳这儿。。
。
。
開始我们把数都不模。。。
能够得到一个规律
n:1 ans:1 4^0
n:2 ans:2 2*(4^0)
2
5 4^0+4^1 4 10
2*(4^0+4^1)
3 21 4^0+4^1+4^2 6
42 2*(4^0+4^1+4^2 )
7 85 4^0+4^1+4^2+4^3 8
170
2*(4^0+4^1+4^2+4^3 )
所以能够看出规律。。
。
。然后我们直接计算。
。
。。。注意不能用等比数列的求和公式。。。。得用分治法中的等比数列求和。。。。。
code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath> using namespace std; typedef __int64 LL; int mod; LL power(LL p,LL n) //高速幂
{
LL sq=1;
while(n>0)
{
if(n%2) sq=sq*p%mod;
n/=2;
p=p*p%mod;
}
return sq;
} LL sum(LL p,LL n) //等比数列求和
{
if(n==0) return 1;
if(n%2)
{
return (sum(p,n/2)*(1+power(p,n/2+1)))%mod;
}
else
{
return (sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;
}
} int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
mod=m;
int ans=0;
if(n&1)
{
ans=sum(4,n/2);
}
else
{
ans=sum(4,n/2-1);
ans*=2;
}
printf("%d\n",ans%mod);
}
return 0;
}
最新文章
- Linux 克隆虚拟机引起的&ldquo;Device eth0 does not seem to be present, delaying initialization&rdquo;
- mongo db 分享 ppt
- excel上传和下载
- ListView控件的用法
- Linux的进程优先级-邹立巍
- [转] Linux文件系统之hard link&;symbol link
- thinkphp中Conf的配置
- Fragment与Activity交互(使用Handler)
- mysql 主从同步 实现增量备份
- TempFile模块
- linux 下使用 tc 模拟网络延迟和丢包
- day10_friest_自动化
- eolinker使用初体验(一)
- [HNOI2008]玩具装箱TOY(斜率优化)
- c# 调试模式下Swaggerf附加接口参数
- [Hanani]JAVA大数相关学习记录
- C# 把字符串中间的多个连续的空格转化成一个空格
- 使用shell数据处理数据实例①-------手把手教学版
- eql高可用部署方案
- 全国Uber优步司机奖励政策 (1月25日-1月31日)