hdu 3802 Ipad,IPhone
做完这题后感觉矩阵超级好用。
用了两次矩阵，一次是在求斐波那契数列时，还有就是求后面的根号式。
前面的两个式子直接二分幂就行。
对于后面的式子，首先F[n]可以用快速幂求解，同时利用费马小定理，每次计算都对（p-1）取余，这些都不是问题。
接下来是关键，首先引用下大神的图
所以我们其实只要求2Xn。
建个矩阵array[2][2]={a+b,2,
(2*a*b)%p,a+b}
所以事实上就是求array的（F[n]mod（p-1））次方，再对求出来的矩阵的第0行，第0个数乘以二再mod p就得到后面部分的值。
#include<stdio.h>
#include<string.h>
#define LL long long
long long p,a,b,n;
struct node
{
long long array[2][2];
};
long long qiumi(long long cur,long long s)//二分幂
{
long long ans=1;
while(s>0)
{
if(s&1)ans*=cur;
cur*=cur;
s/=2;
cur%=p;
ans%=p;
}
return ans;
}
node calcu(node a,node b,int mod)//矩阵乘法
{
int i,j,k;
node ans;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
ans.array[i][j]=0;
for(k=0;k<2;k++)
ans.array[i][j]+=a.array[i][k]*b.array[k][j];
ans.array[i][j]=ans.array[i][j]%mod;
}
return ans;
}
long long zhishu(long long s)//求F[s]的值
{
if(s==0)return 1;
s--;
node tmp,ans;
int i,j,k;
tmp.array[0][0]=1;ans.array[0][0]=1;
tmp.array[0][1]=1;ans.array[0][1]=0;
tmp.array[1][0]=1;ans.array[1][0]=0;
tmp.array[1][1]=0;ans.array[1][1]=1;
while(s>0)
{
if(s&1)ans=calcu(ans,tmp,p-1);
tmp=calcu(tmp,tmp,p-1);
s/=2;
}
return (ans.array[0][0]+ans.array[0][1])%(p-1);
}
long long fbnq(long long s)//求后面的值
{
node tmp,ans;
int i,j,k;
tmp.array[0][0]=(a+b)%p;ans.array[0][0]=1;
tmp.array[0][1]=2;ans.array[0][1]=0;
tmp.array[1][0]=(2*a*b)%p;ans.array[1][0]=0;
tmp.array[1][1]=(a+b)%p;ans.array[1][1]=1;
while(s>0)//矩阵链乘<SPAN style="BACKGROUND-COLOR: rgb(255,255,255)">二分幂</SPAN>
{
if(s&1)ans=calcu(ans,tmp,p);
tmp=calcu(tmp,tmp,p);
s/=2;
}
return ans.array[0][0];
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&p);
if(p==1)
{
printf("0\n");
continue;
}
long long ans;
ans=(qiumi(a,(p-1)/2)+1)*(qiumi(b,(p-1)/2)+1)%p;
//printf("ans=%I64d\n",ans);
long long tmp=zhishu(n);
//printf("tmp=%I64d\n",tmp);
long long ss=2*fbnq(tmp)%p;
//printf("ss=%I64d\n",ss);
printf("%I64d\n",ans*ss%p);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define LL long long
long long p,a,b,n;
struct node
{
long long array[2][2];
};
long long qiumi(long long cur,long long s)//二分幂
{
long long ans=1;
while(s>0)
{
if(s&1)ans*=cur;
cur*=cur;
s/=2;
cur%=p;
ans%=p;
}
return ans;
}
node calcu(node a,node b,int mod)//矩阵乘法
{
int i,j,k;
node ans;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
ans.array[i][j]=0;
for(k=0;k<2;k++)
ans.array[i][j]+=a.array[i][k]*b.array[k][j];
ans.array[i][j]=ans.array[i][j]%mod;
}
return ans;
}
long long zhishu(long long s)//求F[s]的值
{
if(s==0)return 1;
s--;
node tmp,ans;
int i,j,k;
tmp.array[0][0]=1;ans.array[0][0]=1;
tmp.array[0][1]=1;ans.array[0][1]=0;
tmp.array[1][0]=1;ans.array[1][0]=0;
tmp.array[1][1]=0;ans.array[1][1]=1;
while(s>0)
{
if(s&1)ans=calcu(ans,tmp,p-1);
tmp=calcu(tmp,tmp,p-1);
s/=2;
}
return (ans.array[0][0]+ans.array[0][1])%(p-1);
}
long long fbnq(long long s)//求后面的值
{
node tmp,ans;
int i,j,k;
tmp.array[0][0]=(a+b)%p;ans.array[0][0]=1;
tmp.array[0][1]=2;ans.array[0][1]=0;
tmp.array[1][0]=(2*a*b)%p;ans.array[1][0]=0;
tmp.array[1][1]=(a+b)%p;ans.array[1][1]=1;
while(s>0)//矩阵链乘二分幂
{
if(s&1)ans=calcu(ans,tmp,p);
tmp=calcu(tmp,tmp,p);
s/=2;
}
return ans.array[0][0];
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&p);
if(p==1)
{
printf("0\n");
continue;
}
long long ans;
ans=(qiumi(a,(p-1)/2)+1)*(qiumi(b,(p-1)/2)+1)%p;
//printf("ans=%I64d\n",ans);
long long tmp=zhishu(n);
//printf("tmp=%I64d\n",tmp);
long long ss=2*fbnq(tmp)%p;
//printf("ss=%I64d\n",ss);
printf("%I64d\n",ans*ss%p);
}
return 0;
}
补充：软件开发 , C++ ,
