hdu2842

hdu2842 Chinese Rings
传送门
一根木棒上穿了n枚戒指，第一枚戒指取下或者套上需要一步，第k+2枚戒指取下或者套上需要前k枚戒指取下，并且第k+1枚戒指未取下，消耗一步。求出取下n枚戒指所需要的最小步数。

设取下前n枚戒指所需要的最小步数为f(n)，则取下第n枚戒指需要先取下前n-2枚戒指，再取下第n枚，然后套上前n-2枚（互逆过程，和取下前n-2枚的步数一样），变成了取下前n-1枚所需要的最小步数。

[f(n)=f(n-2)+1+f(n-2)+f(n-1) ]

[=f(n-1)+2*f(n-2)+1 ]

[left[egin{matrix}f(n)\f(n-1)\f(n-2)\1end{matrix} ight]=left[egin{matrix}1&2&0&1\1&0&0&0\0&1&0&0\0&0&0&1end{matrix} ight]left[egin{matrix}f(n-1)\f(n-2)\f(n-3)\1end{matrix} ight] ]

[f(2)=2,f(1)=1,f(0)=0 ]

[left[egin{matrix}f(n)\f(n-1)\f(n-2)\1end{matrix} ight]=left[egin{matrix}1&2&0&1\1&0&0&0\0&1&0&0\0&0&0&1end{matrix} ight]^{n-2}left[egin{matrix}2\1\0\1end{matrix} ight] ]

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define pi acos(-1.0)
#define lowbit(x) x&(-x)
using namespace std;

typedef vector<LL> vec;
typedef vector<vec> mat;

const int mod=200907;
LL n;

mat mul(mat A,mat B){
    int a=A.size(),b=B[0].size(),c=B.size();
    mat C(a,vec(b));
    for(int i=0;i<a;i++){
        for(int k=0;k<c;k++){
            for(int j=0;j<b;j++){
                C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
            }
        }
    }
    return C;
}

mat qp(mat A,LL k){
    int a=A.size();
    mat B(a,vec(a));
    for(int i=0;i<a;i++) B[i][i]=1;
    while(k){
        if(k&1) B=mul(B,A);
        A=mul(A,A);
        k>>=1;
    }
    return B;
}

int main(){
    while(scanf("%lld",&n)!=EOF && n){
        if(n==1){
            printf("1
");
            continue;
        }
        if(n==2){
            printf("2
");
            continue;
        }
        n-=2;
        mat A(4,vec(4));
        A[0][0]=A[0][3]=A[1][0]=A[2][1]=A[3][3]=1;
        A[0][1]=2;
        A=qp(A,n);
        LL ans=((A[0][0]*2%mod+A[0][1])%mod+A[0][3])%mod;
        printf("%lld
",ans);
    }
    return 0;
}