首页 > ACM题库 > HDU-杭电 > HDU 4686-Arc of Dream-快速幂-[解题报告]HOJ
2015
09-17

HDU 4686-Arc of Dream-快速幂-[解题报告]HOJ

Arc of Dream

问题描述 :

An Arc of Dream is a curve defined by following function:
Prince and Princess

where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

输入:

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

输出:

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

样例输入:

1
1 2 3
4 5 6
2
1 2 3
4 5 6
3
1 2 3
4 5 6

样例输出:

4
134
1902

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4686

题意:

Arc of Dream

其中a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY

最后的结果mod 1,000,000,007

n<=10^18.

分析:ai*bi=(ai-1 *ax+ay)*(bi-1 *bx+by)

                =(ai-1 * bi-1 *ax*bx)+(ai-1 *ax*by)+(bi-1 *bx*ay)+(ay*by)

设p=ax*bx,  q=ax*by,  r=ay*bx,  s=ay*by

所以ai*bi=p(ai-1 * bi-1)+q(ai-1)+r(bi-1)+s

虽然可以用递推来求出每一项,但是n太大了,直接求绝对会超时的。

设f(n)=an*bn,  a(n)=an,  b(n)=bn

s(n)=sum(ai*bi),i=0,1,…n

则f(i)=p*f(i-1)+q*a(i-1)+r*b(i-1)+s

这是一个递推式,对于任何一个递推式,我们都可以用矩阵法来优化,加快速度求出第n项或前n项和。

我们可以构造一个5*5的矩阵A,使得

【f(n-1),a(n-1),b(n-1),1,s(n-2)】*A=【f(n),a(n),b(n),1,s(n-1)】

=【p*f(n-1)+q*a(n-1)+r*b(n-1)+s, a(n-1)*ax+ay, b(n-1)*bx+by, 1, s(n-2)+f(n-1)】

所以我们容易得出矩阵A: 【   axbx    0   0   0   1

                                          axby   ax   0   0   0

                                          aybx    0   bx  0   0

                                         ayay   ay  by   1   0

                                         0         0    0    0   1 】

由【f(1), a(1) ,b(1), 1, s(0)】*A = 【f(2), a(2), b(2), 1, s(1)】

以此类推得,【f(1), a(1) ,b(1), 1, s(0)】*A^(n-1) = 【f(n), a(n), b(n), 1, s(n-1)】

这样就可以快速的求出s(n-1)了,

其中f(1)=a1*b1, a(1)=a0*ax+ay,

b(1)=b0*bx+by, s(0)=a0*b0

接下来就是矩阵快速幂了。

注意:n==0时,直接输出0,不然会死循环TLE的,还有就是要用long long,也要记得mod

AC代码如下:

 #include<stdio.h>
 #include<string.h>
 //#define LL __int64
 #define LL long long
 #define M 1000000007
 struct Matrix
 {
     LL a[6][6];
 }origin,res,tmp,A,ans;
 int n;
 Matrix mul(Matrix x,Matrix y)
 {
     int i,j,k;
     memset(tmp.a,0,sizeof(tmp.a));
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
             for(k=1;k<=n;k++)
             {
                 tmp.a[i][j]+=(x.a[i][k]*y.a[k][j])%M;
                 tmp.a[i][j]%=M;
             }
     return tmp;
 }
 void quickpow(LL k)
 {
     int i;
     memset(res.a,0,sizeof(res.a));
     for(i=1;i<=n;i++)
         res.a[i][i]=1;
     while(k)
     {
         if(k&1)
             res=mul(res,A);
         A=mul(A,A);
         k>>=1;
     }
 }
 int main()
 {
     LL N,a0,ax,ay,b0,bx,by;
     LL f1,a1,b1,s0;
 //    while(scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d",&N,&a0,&ax,&ay,&b0,&bx,&by)!=EOF)
     while(scanf("%lld %lld %lld %lld %lld %lld %lld",&N,&a0,&ax,&ay,&b0,&bx,&by)!=EOF)
     {
         if(N==0)
         {
             printf("0\n");
             continue;
         }
         a1=(a0*ax+ay)%M;
         b1=(b0*bx+by)%M;
         f1=(a1*b1)%M;
         s0=(a0*b0)%M;
         n=5;
         memset(origin.a,0,sizeof(origin.a));
         origin.a[1][1]=f1;
         origin.a[1][2]=a1;
         origin.a[1][3]=b1;
         origin.a[1][4]=1;
         origin.a[1][5]=s0;
         memset(A.a,0,sizeof(A.a));
         A.a[1][1]=(ax*bx)%M;
         A.a[1][5]=1;
         A.a[2][1]=(ax*by)%M;
         A.a[2][2]=ax%M;
         A.a[3][1]=(ay*bx)%M;
         A.a[3][3]=bx%M;
         A.a[4][1]=(ay*by)%M;
         A.a[4][2]=ay%M;
         A.a[4][3]=by%M;
         A.a[4][4]=1;
         A.a[5][5]=1;
 
         quickpow(N-1);
         ans=mul(origin,res);
     //    printf("%I64d\n",ans.a[1][5]);
         printf("%lld\n",ans.a[1][5]);
     }
     return 0;
 }

 

 

参考:http://www.cnblogs.com/frog112111/archive/2013/08/21/3273660.html