CodeForces 1182E Product Oriented Recurrence

题意

给定五个整数 \(n,f_1,f_2,f_3,c\)，其中数列 \(f\) 满足以下递推式：

\[f_x=c^{2x-6}f_{x-1}f_{x-2}f_{x-3}
\]

求 \(f_n\)。

\(\texttt{Data Range:}4\leq n\leq 10^{18},1\leq f_1,f_2,f_3,c\leq 10^9\)

题解

矩阵快速幂。

首先这个乘起来的东西显然没有什么方法去递推，然而从递推式中可以直接看出 \(f_n\) 是类似于 \(c^gf_1^{i}f_2^{j}f_3^{k}\) 的形式，所以考虑把每个次数算出来然后快速幂。

注意到这个次数很好算的。设 \(f_n\) 中 \(c\) 的次数为 \(g_n\)，那么显然有递推式

\[g_n=2n-6+g_{n-1}+g_{n-2}+g_{n-3}=2(n-1)-4+g_{n-1}+g_{n-2}+g_{n-3}
\]

注意到这个东西是常见的非齐次线性递推模样，于是可以高高兴兴的走一波矩阵：

\[\begin{pmatrix}g_n\\g_{n-1}\\g_{n-2}\\n\\1\end{pmatrix}=\begin{pmatrix}1&1&1&2&-4\\1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&1\\0&0&0&0&1\end{pmatrix}\begin{pmatrix}g_{n-1}\\g_{n-2}\\g_{n-3}\\n-1\\1\end{pmatrix}
\]

然后考虑递推 \(f_1,f_2,f_3\) 的次数。以 \(f_1\) 为例，设 \(f_n\) 中 \(f_1\) 的次数为 \(h_n\)，那么有

\[h_n=h_{n-1}+h_{n-2}+h_{n-3}
\]

这个转移矩阵挺好写的，也就是：

\[\begin{pmatrix}h_n\\h_{n-1}\\h_{n-2}\end{pmatrix}=\begin{pmatrix}1&1&1\\1&0&0\\0&1&0\end{pmatrix}\begin{pmatrix}h_{n-1}\\h_{n-2}\\h_{n-3}\end{pmatrix}
\]

同时注意到 \(f_2\) 和 \(f_3\) 次数的递推式也是这个东西，只不过 \(h_1,h_2,h_3\) 不同而已，于是这个也可以递推出来了，然后就做完了。

代码

#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

const ll MAXN=2e5+51,MOD=1e9+7;

struct Matrix{

    ll num[6][6];

    Matrix()

    {

        memset(num,0,sizeof(num));

    }

    inline ll* operator [](const ll &x)

    {

        return num[x];

    }

    inline const ll* operator [](const ll &x)const

    {

        return num[x];

    }

};

Matrix mat,mat2,x,x2;

ll f1,f2,f3,c,res;

li n;

inline li read()

{

    register li num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline ll qpow(ll base,ll exponent)

{

    ll res=1;

    while(exponent)

    {

        if(exponent&1)

        {

            res=(li)res*base%MOD;

        }

        base=(li)base*base%MOD,exponent>>=1;

    }

    return res;

}

inline Matrix operator *(Matrix x,Matrix y)

{

    Matrix res;

    for(register int i=1;i<=5;i++)

    {

        for(register int j=1;j<=5;j++)

        {

            for(register int k=1;k<=5;k++)

            {

                res[i][j]=(res[i][j]+(li)x[i][k]*y[k][j]%(MOD-1))%(MOD-1);

            }

        }

    }

    return res;

}

inline Matrix qpow(Matrix base,li exponent)

{

    Matrix res;

    for(register int i=1;i<=5;i++)

    {

        res[i][i]=1;

    }

    while(exponent)

    {

        if(exponent&1)

        {

            res=res*base;

        }

        base=base*base,exponent>>=1;

    }

    return res;

}

int main()

{

    n=read(),f1=read(),f2=read(),f3=read(),c=read(),res=1;

    mat[1][1]=mat[2][1]=mat[3][1]=mat[1][2]=mat[2][3]=mat[4][4]=mat[5][4]=1;

    mat[5][5]=x[1][5]=mat2[1][1]=1,mat[4][1]=2,mat[5][1]=MOD-5,x[1][4]=3;

    mat2[2][1]=mat2[3][1]=mat2[1][2]=mat2[2][3]=x2[1][3]=1;

    res=qpow(c,(x*qpow(mat,n-3))[1][1]);

    res=(li)res*qpow(f1,(x2*qpow(mat2,n-3))[1][1])%MOD,x2[1][3]=0,x2[1][2]=1;

    res=(li)res*qpow(f2,(x2*qpow(mat2,n-3))[1][1])%MOD,x2[1][2]=0,x2[1][1]=1;

    res=(li)res*qpow(f3,(x2*qpow(mat2,n-3))[1][1])%MOD,printf("%d\n",res);

}

巴特西

CodeForces 1182E Product Oriented Recurrence

题意

题解

代码

最新文章

热门文章