HDU2842—Chinese Rings

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2842

题目意思：一把一个n连环的前n个拿下来，一个个n连环，要把第k个拿下来，需要把前n-2个拿下来，并留下第n-1个环，然后花一步把第n个拿下来，然后为了把第n-1个环拿下来，我们又需要把前n-2个放回去（逆过程），从而把这个问题转化成把前n-1个环拿下来。

思路：根据上面的分析，我们很容易的可以写出递推式子，f[n]=2*f[n-2]+f[n-1]+1,一个带常数项的矩阵快速幂，题目意思有点难懂，忽略了，要把前n-2个放回去，还是逆过程，一直没有搞得特别懂，感觉有点没道理。

代码：

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define n 3

#define MOD 200907

using namespace std;

typedef long long ll;

struct Matrix{

    ll mat[][];

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

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

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

                tmp.mat[i][j]=;

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

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;

                    tmp.mat[i][j]%=MOD;

                }

            }

        return tmp;

    }

};

Matrix POW(Matrix m,ll k){

    Matrix ans;

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

    for(int i=;i<n;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    ll num;

    while(cin>>num&&num){

        Matrix m;

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

        m.mat[][]= m.mat[][]= m.mat[][]= m.mat[][]=;

        m.mat[][]=;

        ll f[]={,,};

        Matrix ans;

        if(num<=) cout<<(num==?:)<<endl;

        else{

            ans=POW(m,num-);

            ll sum=;

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

                sum+=ans.mat[][i]*f[i]%MOD;

            }

            cout<<sum%MOD<<endl;

        }

    }

    return ;

}