HDOJ 4686 Arc of Dream

HDOJ题目页面传送门

有\(2\)个数列\(a:a_i=\begin{cases}a0&i=0\\ax\cdot a_{i-1}+ay&i>0\end{cases},b:b_i=\begin{cases}b0&i=0\\bx\cdot b_{i-1}+by&i>0\end{cases}\)。给定\(n,a0,ax,ay,b0,bx,by\)，求\(\sum\limits_{i=0}^{n-1}a_ib_i\)，答案对\(10^9+7\)取模。

\(n\in\left[0,10^{18}\right]\)。

显然是矩阵快速幂。。

\(a_i,b_i\)肯定是要放到向量里去的。要求的是\(\sum\limits_{i=0}^{n-1}a_ib_i\)，所以我们可以记录一个前缀和\(Sum_i=\sum\limits_{j=0}^{i}a_jb_j\)放到向量里。\(a,b\)的递推式里分别有\(ay,by\)这一项，可以看作\(ay\cdot1,by\cdot1\)，于是再往向量里放一个\(1\)。

然而现在还是不能通过向量里的几个东西乘以个系数凑出\(Sum\)的递推式。因为\(Sum_i=Sum_{i-1}+a_ib_i=Sum_{i-1}+(ax\cdot a_{i-1}+ay)(bx\cdot b_{i-1}+by)=ax\cdot bx\cdot a_{i-1}b_{i-1}+ax\cdot by\cdot a_{i-1}+ay\cdot bx\cdot b_{i-1}+ay\cdot by\)，里面包含了\(a_{i-1}b_{i-1}\)这一项无法凑出。不妨将\(a_ib_i\)也放到向量里，这样\(a_ib_i\)和\(Sum_i\)都有递推式了。

令\(\Delta\times \begin{bmatrix}1\\a_{i-1}\\b_{i-1}\\a_{i-1}b_{i-1}\\Sum_{i-1}\end{bmatrix}=\begin{bmatrix}1\\a_i\\b_i\\a_ib_i\\Sum_i\end{bmatrix}\)，容易得到\(\Delta=\begin{bmatrix}1&0&0&0&0\\ay&ax&0&0&0\\by&0&bx&0&0\\ay\cdot by&ax\cdot by&ay\cdot bx&ax\cdot bx&0\\ay\cdot by&ax\cdot by&ay\cdot bx&ax\cdot bx&1\end{bmatrix}\)。那么答案就是\(\left(\Delta^{n-1}\times\begin{bmatrix}1\\a_0\\b_0\\a_0b_0\\Sum_0\end{bmatrix}\right)_{5,1}=\left(\Delta\times\begin{bmatrix}1\\a0\\b0\\a0\cdot b0\\a0\cdot b0\end{bmatrix}\right)_{5,1}\)。

最后吐槽一下HDOJ题面的不严谨：没有交代\(n\)的下界，导致我没有特判\(n=0\)的情况。\(n=0\)应直接输出\(0\)，如果带到式子里算的话，\(n-1=-1\)，作为快速幂的指数会TLE……

下面贴代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
struct matrix{//矩阵 
    int a[5][5];
    int *operator[](int x){return a[x];}
    matrix(){memset(a,0,sizeof(a));}//零矩阵 
    matrix(int){for(int i=0;i<5;i++)for(int j=0;j<5;j++)a[i][j]=i==j;}//单位矩阵 
    friend matrix operator*(matrix x,matrix y){//矩阵乘法 
        matrix res;
        for(int i=0;i<5;i++)for(int j=0;j<5;j++)for(int k=0;k<5;k++)
            res[i][j]+=x[i][k]*y[k][j]%mod;
        return res;
    }
    matrix operator*=(matrix y){return *this=*this*y;}
    friend matrix operator^(matrix x,int y){//矩阵快速幂 
        matrix res(0);
        while(y){
            if(y&1)res*=x;
            x*=x;
            y>>=1;
        }
        return res;
    }
    matrix operator^=(int y){return *this=*this^y;}
};
signed main(){
    int n,a0,ax,ay,b0,bx,by;
    while(cin>>n>>a0>>ax>>ay>>b0>>bx>>by){
        if(n==0){puts("0");continue;}//特判n=0 
        matrix delta;//递推矩阵 
        delta[0][0]=1;delta[0][1]=0;delta[0][2]=0;delta[0][3]=0;delta[0][4]=0;
        delta[1][0]=ay;delta[1][1]=ax;delta[1][2]=0;delta[1][3]=0;delta[1][3]=0;
        delta[2][0]=by;delta[2][1]=0;delta[2][2]=bx;delta[2][3]=0;delta[2][3]=0;
        delta[3][0]=ay*by%mod;delta[3][1]=ax*by%mod;delta[3][2]=ay*bx%mod;delta[3][3]=ax*bx%mod;delta[3][4]=0;
        delta[4][0]=ay*by%mod;delta[4][1]=ax*by%mod;delta[4][2]=ay*bx%mod;delta[4][3]=ax*bx%mod;delta[4][4]=1;
        delta^=n-1;
        cout<<(delta[4][0]+delta[4][1]*a0%mod+delta[4][2]*b0+delta[4][3]*a0%mod*b0%mod+delta[4][4]*a0%mod*b0%mod)%mod<<"\n";
    }
    return 0;
}

原文链接:https://www.cnblogs.com/ycx-akioi/p/HDOJ-4686.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有