2017 ACM-ICPC 亚洲区（西安赛区）网络赛b题Coin(矩阵快速幂)

题意：给出抛一个硬币正面向上的概率，求抛k次，有偶数次向上的概率，用x乘y的逆元来表示
y的逆元可以用扩展欧几里得求，难点在于求x，显然y等于p的k次方，然后x等于（（p-q）+p）的k次方里含p的偶数次方项的和。比赛时想了很久，突然发现，和求⌈(a+b√n⌉%m有点类似，于是想到矩阵快速幂。代码如下

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const long long mod= 1e9+7;
long long exgcd(long long a,long long b,long long &x,long long &y)//拓展欧几里得
{
if(b==0)
{
x=1,y=0;
return a;
}
long long ret=exgcd(b,a%b,x,y);
long long tmp=x;
x=y;
y=tmp-a/b*y;
return ret;
//返回（a，b）
}
long long mod_pow(long long x, long long n, long long mod)//快速幂取模
{
long long res = 1;
x = x % mod;
while(n > 0)
{
if(n & 1)
{
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
struct Matrix
{
long long ma[2][2];
};
Matrix mul(const Matrix &a,const Matrix &b)
{
Matrix c;
memset(c.ma,0,sizeof(c.ma));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c.ma[i][j]=(c.ma[i][j]+a.ma[i][k]*b.ma[k][j])%mod;
}
}
}
return c;
}
Matrix qmul(Matrix a,int k)//矩阵快速幂
{
Matrix b;memset(b.ma,0,sizeof(b.ma));
for(int i=0;i<2;i++) b.ma[i][i]=1;
while(k>0)
{
if(k&1) b=mul(b,a);
a=mul(a,a);
k/=2;
}
return b;
}
int main()
{
long long T,q,p,k;
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&p,&q,&k);
long long xx,yy;
Matrix a;
a.ma[0][0]=p-q;a.ma[1][1]=p-q;//构造矩阵
a.ma[0][1]=q;a.ma[1][0]=q;
Matrix ans=qmul(a,k-1);
long long x1=((p-q)*ans.ma[0][0]+q*ans.ma[1][0])%mod;
p=mod_pow(p,k,mod);
exgcd(p,mod,xx,yy);
xx=(xx%mod+mod)%mod;
long long ans1=(x1*xx)%mod;
printf("%lldn",ans1);
}return 0;
}

最后

以上就是顺心绿草为你收集整理的2017 ACM-ICPC 亚洲区（西安赛区）网络赛b题Coin(矩阵快速幂)的全部内容，希望文章能够帮你解决2017 ACM-ICPC 亚洲区（西安赛区）网络赛b题Coin(矩阵快速幂)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。