HDU 3802 Ipad,IPhone
2024-08-25 23:44:00
http://wutyyzchangde.blog.163.com/blog/static/172226566201132311311374/
#include <cstdio>
typedef struct{
__int64 matrix[2][2];
}Matrix;
__int64 powermod(__int64 x,__int64 n,__int64 p){
__int64 res = 1;
for(;n;n>>=1){
if(n&1)
res=(res*x)%p;
x=(x*x)%p;
}
return res;
}
Matrix multi(Matrix x,Matrix y,__int64 p){
Matrix res;
int i,j,k;
__int64 sum;
for(i=0;i<2;i++)
for(j=0;j<2;j++){
sum=0;
for(k=0;k<2;k++)sum+=(x.matrix[i][k]*y.matrix[k][j])%p;
res.matrix[i][j] = sum%p;
}
return res;
}
Matrix Mat_powermod(Matrix x,__int64 n,__int64 p){
Matrix res;
int i,j;
for(i=0;i<2;i++)
for(j=0;j<2;j++){
if(i==j)
res.matrix[i][j] = 1;
else res.matrix[i][j] = 0;
}
for(;n;n>>=1){
if(n&1)res=multi(res,x,p);
x=multi(x,x,p);
}
return res;
}
int main(){
__int64 p,T,a,b,n;
__int64 keep1,keep2,keep3;
__int64 power,result;
Matrix res;
scanf("%I64d",&T);
while(T--){
scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&p);
keep1=(powermod(a,(p-1)/2,p)+1)%p;
keep2=(powermod(b,(p-1)/2,p)+1)%p;
if(n==0)power=1;
else{
res.matrix[0][0] = 1;
res.matrix[0][1] = 1;
res.matrix[1][0] = 1;
res.matrix[1][1] = 0;
res=Mat_powermod(res,n-1,p-1);
power=(res.matrix[0][0]+res.matrix[0][1])%(p-1);
}
power+=p-1;
res.matrix[0][0]=(a+b)%p;
res.matrix[0][1]=(2*a*b)%p;
res.matrix[1][0]=2%p;
res.matrix[1][1]=(a+b)%p;
res=Mat_powermod(res,power-1,p);
keep3=(2*(((res.matrix[0][0]*(a+b))%p+(res.matrix[0][1]*2)%p)%p))%p;
result=1;
result=(result*keep1)%p;
result=(result*keep2)%p;
result=(result*keep3)%p;
printf("%I64d\n",result);
}
return 0;
}
最新文章
- 【初探移动前端开发04】jQuery Mobile (中)
- swift导航栏导航按钮添加多个按钮事件
- 对iOS中Delegate的理解
- PMP - 项目管理思维导图
- python 代码片段25
- mybitis学习的页面
- centos 7 u盘安装
- 在Dll中使用 TFDQuery 的 LoadFromStream 方法注意问题
- Java实现Linux下服务器程序的双守护进程
- poj3273 二分
- Jquery文本框值改变事件(支持火狐、ie)
- 【ShaderToy】跳动的心❤️
- redis哨兵主从自动切换
- 将nginx永久加入到系统环境变量
- Postgres数据库维护
- 分布式任务调度系统xxl-job源码探究(二、服务中心)
- python爬虫 bs4_4select()教程
- Oracle 11gR2 Database UNDO表空间使用率居高不下处理
- Golang 处理 Json(二):解码
- 4. mybatis 的排序
热门文章
- C# Attribute(特性)之---契约---[ServiceContract] 、 [OperationContract]
- 【转】在Spring中基于JDBC进行数据访问时怎么控制超时
- IM,游戏服务端 tcp 框架整理
- C#学习日志 day 2 ------ 控制台颜色以及windowsphone 窗体应用试建
- ngCookies模块
- Win7下使用protel99se、protel99
- css 自适应布局
- php执行shell更新svn文件的方法
- android 关于多任务下载问题
- POJ 2758 Checking the Text(Hash+二分答案)