Loading...

洛谷P1939 [模板]矩阵加速(数列)

check评论:0 条 remove_red_eye浏览量:610 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-30

$a[1]=a[2]=a[3]=1,a[n]=a[n-1]+a[n-3](4\leq n)$,多组询问求出$a[n]$

这道题一看$100$次询问,$n=2e9$就知道要用矩阵快速幂

我们得到的式子是$\begin{matrix} ? & ? &?\\ ? & ? & ? \\?&?&?\end{matrix}$ $\times$ $\begin{matrix} a[3]\\a[2]\\a[1]\end{matrix}$=$\begin{matrix}a[4]\\a[3]\\a[2]\end{matrix}$

因为$a[4]=a[3]+a[1]$,所以矩阵的第一行的第一位和第三位贡献为$1$

因为$a[3]$和$a[2]$只能由自己得到,所以第二行的第一位和第三行的第二位贡献为$1$

就可以得到矩阵乘法的式子$\begin{matrix} 1 & 0 &1\\ 1 & 0 & 0 \\0&0&1\end{matrix}$ $\times$ $\begin{matrix} a[3]\\a[2]\\a[1]\end{matrix}$=$\begin{matrix}a[4]\\a[3]\\a[2]\end{matrix}$

然后裸的矩阵快速幂就好

#include <bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
struct mat
{
    int qwq[4][4];
    void clear()
    {
        memset(qwq,0,sizeof(qwq));
        qwq[1][1]=qwq[1][3]=qwq[2][1]=qwq[3][2]=1;
    }
};
int ma[4][2];
void clear()
{
    ma[1][1]=ma[2][1]=ma[3][1]=1;
}
mat mul(mat a,mat b)
{
    mat c;
    memset(c.qwq,0,sizeof(c.qwq));
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int k=1;k<=3;k++)
            {
                c.qwq[i][j]+=a.qwq[i][k]*b.qwq[k][j];
                c.qwq[i][j]%=mod;
            }
        }
    }
    return c;
}
mat ksm(int b)
{
    mat qaq,chu;
    qaq.clear();
    memset(chu.qwq,0,sizeof(chu.qwq));
    for(int i=1;i<=3;i++)
    {
        chu.qwq[i][i]=1;
    }
    while(b)
    {
        if(b&1)
        {
            chu=mul(chu,qaq);
        }
        qaq=mul(qaq,qaq);
        b>>=1;
    }
    return chu;
}
main()
{
    int t;
    cin>>t;
    clear();
    while(t--)
    {
        int x;
        scanf("%lld",&x);
        if(x<=3)
        {
            printf("1\n");
            continue;
        }
        mat a=ksm(x-3);
        int ans=0;
        for(int i=1;i<=3;i++)
        {
            ans+=a.qwq[1][i]*ma[i][1];
            ans%=mod;
        }
        cout<<ans<<endl;
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名