Codevs 1305 Freda的道路(矩阵乘法 DP优化)

1305 Freda的道路

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

Freda要到Rainbow的城堡去玩了。我们可以认为两座城堡位于同一条数轴上，Freda的城堡坐标是0，Rainbow的城堡坐标是N。正常情况下，Freda会朝着同一个方向（即Rainbow的城堡相对于Freda的城堡的方向）走若干步之后来到Rainbow的城堡，而且步长都为1或2。可是，今天Freda在途中遇见了来自上海的小猫Resodo，惊奇之下，居然有一步走反了方向！不过，Freda并没有神智不清，它只有一步走反了方向，而且这一步的步长也是1或2. 同时，Freda并不会路过Rainbow的城堡而不停下来。当然，Freda是在途中遇到Resodo的，所以它不会在自己家门口就走错方向。

举个例子，如果Rainbow的城堡坐标是3，那么下面两条路径是合法的：

0->1->2->1->3

0->1->-1->1->3

当然，还有其它的合法路径。下面这些路径则是不合法的：

0->-1->1->3 （Freda不可能第一步就走错方向）

0->1->3（Freda一定是有一步走错方向的）

0->2->1->0->2->3（Freda只有一步是走错方向的）

0->-1->0->3（Freda每步的长度一定是1或2）

0->1->2->4->3（Freda不会越过Rainbow的城堡再回来）

0 -> 1 -> 2 -> 3 -> 2 -> 3（Freda一旦到达了Rainbow的城堡，就会停下来）

你现在需要帮助Freda求出，它一共有多少种方法能够到达Rainbow的城堡呢？

输入描述 Input Description

一行一个整数N，表示Rainbow城堡的坐标

输出描述 Output Description

一行一个整数，表示Freda到Rainbow城堡的不同路径数。由于这个数字可能很大，你只需要输出它mod 1000000007的结果。

样例输入 Sample Input

2

样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

对于第一组样例，如下5条路径是合法的：

0->1->0->2

0->1->-1->0->1->2

0->1->-1->0->2

0->1->0->1->2

0->1->-1->1->2

数据范围与约定

对于10%的数据，N<=20.

对于70%的数据，N<=1000.

对于90%的数据，N<=1000000.

对于100%的数据，N<=10^15.

分类标签 Tags

动态规划矩阵乘法数论

/*

矩阵乘法 DP优化.

这题一开始激动了,以为多扩展两项就OK 然后全W了.

如果一开始没有沙茶想法的话去想DP的话,

这题应该能自己做出来.

设DP状态.

f[i][0/1]走到i有无回头的不同路径条数.

显然的有

f[i][0]=f[i-1][0]+f[i-2][0].

f[i][1]=f[i-1][1]+f[i-2][1]+f[i+1][0]+f[i+2][0].

然后我们惊喜地发现递推能得90分2333.

f[i][1]只与f[i-1][1],f[i-2][1],f[i+1][0],f[i+2][0]有关.

然后搞个4*4的矩阵 自己推一推就好了.

*/

#include<iostream>

#include<cstdio>

#define LL long long

#define mod 1000000007

using namespace std;

LL n,ans[5][5],c[5][5];

LL b[5][5]={{0,0,0,0,0},{0,1,0,0,1},{0,1,1,1,0},{0,1,1,0,0},{0,1,0,0,0}};

void mi()

{

    while(n)

    {

        if(n&1)

        {

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

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

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

                  c[i][j]=(c[i][j]+ans[i][k]*b[k][j]%mod)%mod;

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

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

                ans[i][j]=c[i][j],c[i][j]=0;

        }

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

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

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

              c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod;

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

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

            b[i][j]=c[i][j],c[i][j]=0;

        n>>=1;

    }

}

void slove()

{

    n-=2;

    ans[1][1]=5,ans[1][2]=8,ans[1][3]=5,ans[1][4]=0;

    mi();

}

int main()

{

    cin>>n;

    if(!n||n==1){printf("1");return 0;}

    else if(n==2) {printf("5");return 0;}

    slove();

    cout<<ans[1][1];

    return 0;

}

巴特西

Codevs 1305 Freda的道路(矩阵乘法 DP优化)

最新文章

热门文章