Chinese Rings

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 46 Accepted Submission(s): 29

Problem Description

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

Source

2009 Multi-University Training Contest 3 - Host by WHU

Recommend

gaojie

/*
题意：给你一个n连环，让你输出解n连环的最少步骤数。定义了一个规则，取下第k个环的要求是，k+1在环上，
    前k+2个不在环上

初步思路：这种题看到1e9的数据量，结果一般都是找规律的。给定n个环和规则：如果想取下第n个环那么要保
    证前n-2都取下，第n-1还在，那么假设F(n) 为接下n的最短时间，那么想要解下n，必须先加下F(n-2),然后
    解下n，然后解下F(n-1),想要解下F(n-1)就要先解下F(n-2)+1,所以得到：f[n]=2*f[n-2]+f[n-1]+1
    
#错误：中间有什么地方爆了int,重载乘号运算符的时候爆了int
*/
#include<bits/stdc++.h>
#define mod 200907
#define ll long long
using namespace std;
/********************************矩阵模板**********************************/
class Matrix {
    public:
        int a[3][3];

        void init(int x) {
            memset(a,0,sizeof(a));
            if(x==1){
                a[0][0]=1;
                a[0][2]=1;
            }else{
                a[0][0]=1;
                a[0][1]=1;
                a[1][0]=2;
                a[2][0]=1;
                a[2][2]=1;
            }
        }

        Matrix operator +(Matrix b) {
            Matrix c;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
            return c;
        }

        Matrix operator +(int x) {
            Matrix c = *this;
            for (int i = 0; i < 3; i++)
                c.a[i][i] += x;
            return c;
        }

        Matrix operator *(Matrix b)
        {
            Matrix p;
            memset(p.a,0,sizeof p.a);
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    p.a[i][j] = (p.a[i][j] + ( (ll)( (ll)a[i][k]* (ll) b.a[k][j])%mod ) )% mod;
            return p;
        }

        Matrix power_1(int t) {
            Matrix ans,p = *this; 
            memset(ans.a,0,sizeof ans.a);
            for(int i=0;i<3;i++){
                ans.a[i][i]=1;
            }
            while (t) {
                if (t & 1)
                    ans=ans*p;
                p = p*p;
                t >>= 1;
            }
            return ans;
        }
        
        Matrix power_2(Matrix a,Matrix b,int x){
            while(x){
                if(x&1){
                    b=a*b;
                }
                a=a*a;
                x>>=1;
            }
            return b;
        }
}unit,init;
/********************************矩阵模板**********************************/
int n;
int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF&&n){
        unit.init(1);
        init.init(0);
        if(n<=1){
            printf("%d
",n);
            continue;
        }
        init=init.power_1(n-1);
        printf("%d
",( (unit*init).a[0][0]+mod )%mod);
    }
    return 0;
}