hdu-2842(矩阵快速幂+推导)

傷城~ 2022-06-09 05:20 352阅读 0赞

问题描述:

Dumbear likes to play the Chinese Rings (Baguenaudier). It’s a game played with nine rings on a bar. The rules of this game are very simple: At first, the nine rings are all on the bar.   
The first ring can be taken off or taken on with one step.   
If the first k rings are all off and the (k + 1)th ring is on, then the (k + 2)th ring can be taken off or taken on with one step. (0 ≤ k ≤ 7)   
  
Now consider a game with N (N ≤ 1,000,000,000) rings on a bar, Dumbear wants to make all the rings off the bar with least steps. But Dumbear is very dumb, so he wants you to help him.

Input

Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number "0".

Output

For each line, output an integer S indicates the least steps. For the integers may be very large, output S mod 200907.

Sample Input

1
    4
    0

Sample Output

1
    10

题目题意:题目给你n个戒指,问最小的步数可以取完所有的戒指，取戒指时，按照如下规则，如果你要取第k+2个戒指，那么第k+1个戒指必须在，且前面k个戒指都取完了。

（可以把戒指放回)

题目分析:关键在于公式的推导吧！我们假设F(n)等于取完n个戒指的最小步数，那么我们想，当我们要取第n个戒指时，那么第n-1在且前面n-2个都取完了，则F(n-2)+1表示取完前n-2个和第n个，那么还有第n-1个怎么办了，我们把n-2个在放回去，那么就变成了取完n-1个戒指，F(n-1)+F(n-2)

那么关系式就是F(n)=F(n-1)+2\*F(n-2)+1;

我们构造如下矩阵:

1  2  0  1            f(n-1)          f(n)

1  0  0  0    \*       f(n-2)   =    f(n-1)

0  1  0  0             f(n-3)         f(n-2)

0  0  0  1               1               1

这个题目，我用int炸了，用long long过的！！!

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int mod=200907;
    
    struct matrix//构建矩阵
    {
        ll f[5][5];
        matrix operator* (const matrix &a) const {
            matrix res;
            for (int i=1;i<=4;i++) {
                for (int j=1;j<=4;j++) {
                    res.f[i][j]=0;
                    for (int k=1;k<=4;k++)
                        res.f[i][j]=(res.f[i][j]+(*this).f[i][k]*a.f[k][j])%mod;
                    res.f[i][j]=(res.f[i][j]%mod+mod)%mod;
                }
            }
            return res;
        }
    }a,b;
    
    void init()
    {
        b.f[1][1]=1,b.f[1][2]=2,b.f[1][4]=1;
        b.f[2][1]=1;
        b.f[3][2]=1;
        b.f[4][4]=1;
        a.f[1][1]=2,a.f[2][1]=1,a.f[3][1]=0,a.f[4][1]=1;
    }
    
    matrix fast_pow(matrix &base,int k)
    {
        matrix ans=base;
        while (k) {
            if (k&1)
                ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            if (n==0) break;
            if (n==1) { printf("%d\n",1); continue;}
            if (n==2) { printf("%d\n",2); continue;}
            n-=3;
            init();
            struct matrix cur,ans;
            cur=b;
            cur=fast_pow(cur,n);
            ans=cur*a;
            printf("%lld\n",ans.f[1][1]);
        }
        return 0;
    }