HDU 1588 矩阵快速幂嵌套矩阵

这个题目搞了我差不多一个下午，之前自己推出一个公式，即 f[n+k]=k*f[n]+f[n-1]结果发现根本不能用，无法降低复杂度。

后来又个博客的做法相当叼，就按他的做法来了

即最终求得是 S（n）=f[b]+f[b+k]+f[b+2*k]....f[b+n*k] (原题的意思好像是不用加到第n项，但实测确实要加到该项)

然后我们令 A={1，1}（标准的斐波那契矩阵）

{1,0}发现 f[b]=A^b,f[b+k]=A^(b+k),....f[b+nk]=A^(b+nk);

提取公共因子 A^b.S(n)=A^b*(E+A^K+A^K^2....A^K^n)

再令K=A^K (K和E都是矩阵，E为单位矩阵)。于是S（n）=A^b*(E+K+k^2+K^3+...K^n);

这样我们的目的大概出来了，就是要尽可能短的算出上式括号中的内容(A^b可以用经典斐波那契矩阵很快算出来)

于是构造一个嵌套矩阵

令 SK={K，E}，（K,E,0均为矩阵），SK^N={K^N , E+K+K^2+K^3+...K^N}

{0，E} {0 , E }

这样只要求出SK^N,取其第一行的第二项再与 A^b相乘，即可得出最终结果

嵌套矩阵跟普通矩阵差不多，调用写好的矩阵乘法即可实现嵌套矩阵的乘法和乘方

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll __int64

using namespace std;

ll k,b,n,M;

struct Mat

{

    ll mat[][];

} Fb,E,zero,A;

struct Smart

{

    Mat d[][];

} SK,SE;

void test(Mat t)

{

    for (int i=;i<;i++)

    {

        for (int j=;j<;j++)

            cout<<t.mat[i][j]<<" ";

        cout<<endl;

    }

}

void test2(Smart tmp)

{

    for (int i=;i<;i++)

    {

        for (int j=;j<;j++)

            test(tmp.d[i][j]);

    }

}

Mat operator +(Mat a,Mat b)

{

    Mat c;

    for (int i=;i<;i++)

    {

        for (int j=;j<;j++)

        {

            c.mat[i][j]=a.mat[i][j]+b.mat[i][j];

            c.mat[i][j]%=M;

        }

    }

    return c;

}

Mat operator *(Mat a,Mat b)

{

    Mat c;

    memset(c.mat,,sizeof c.mat);

    for (int i=;i<;i++)

    {

        for (int j=;j<;j++)

        {

            for (int k=;k<;k++)

            {

                c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];

                if (c.mat[i][j]>=M)

                    c.mat[i][j]%=M;

            }

        }

    }

    return c;

}

Mat operator ^(Mat a,ll x)

{

    //if (x==0) return a;

   // cout<<x<<" the x"<<endl;

    Mat c=E;

    for (;x;x>>=)

    {

        if (x&)

            c=c*a;

        a=a*a;

    }

    return c;

}

Smart operator *(Smart a,Smart b) //大矩阵的乘法 调用普通矩阵的乘法和加法公式即可

{

    Smart c;

    Mat tmp;

    for (int i=;i<;i++)

    {

        for (int j=;j<;j++)

        {

            c.d[i][j]=zero;

            for (int k=;k<;k++)

            {

                tmp=a.d[i][k]*b.d[k][j];

                c.d[i][j]=c.d[i][j]+tmp;

            }

        }

    }

    return c;

}

Smart operator ^(Smart a,ll x) //大矩阵的乘法 调用普通矩阵的乘法公式即可

{

    Smart c=SE;

   // if (x==0) return a;

    //cout<<x<<" the s x "<<endl;

    for (;x;x>>=)

    {

        if (x&)

            c=c*a;

        a=a*a;

      // test2(c);

    }

   // test2(c);

    return c;

}

void init()

{

    memset(zero.mat,,sizeof zero);

    memset(E.mat,,sizeof E.mat);

    for (int i=;i<;i++)

        E.mat[i][i]=;

    Mat A;

    memset(A.mat,,sizeof A.mat);

    SE.d[][]=SE.d[][]=E;

    SE.d[][]=SE.d[][]=zero;

    A.mat[][]=A.mat[][]=A.mat[][]=;

    Fb=A^b;

    //test(Fb);

    SK.d[][]=A^k;

    SK.d[][]=SK.d[][]=E;

    SK.d[][]=zero;

}

int main()

{

    while (scanf("%I64d %I64d %I64d %I64d",&k,&b,&n,&M)!=EOF)

    {

        init();

        Smart s=SK^n;

        Mat tmp=s.d[][];

        //test(tmp);

        Mat ans=Fb*tmp;

        printf("%I64d\n",ans.mat[][]);//因为Fb求出来 真正的 A^b在[1][0]处，但是最终结果为何也是1 0处 我觉得还是有待考究

    }

return ;

}

巴特西

HDU 1588 矩阵快速幂嵌套矩阵

最新文章

热门文章

巴特西

HDU 1588 矩阵快速幂 嵌套矩阵

最新文章

热门文章

HDU 1588 矩阵快速幂嵌套矩阵