本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=2842，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
找到递推公式f(n)=2*f(n-2)+f(n-1)+1;
要想卸下前n个环，要卸先下前n-2个，然后卸下第n个环，然后按上n-2个环，在卸下n-1环。。。。
AC代码：
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 200907
using namespace std;
typedef long long L;
typedef struct str
{ L s[3][3];
}Node;
Node a,b;
Node ceil(Node p,Node q)
{ Node c;memset(c.s,0,sizeof(c.s));for(int i=0;i<3;++i)for(int j=0;j<3;++j)for(int t=0;t<3;++t)c.s[i][j]=(c.s[i][j]+p.s[i][t]*q.s[t][j])%M;return c;
}
Node doit(int k)
{ Node p=a,q=b;while(k){ if(k&1) p=ceil(p,q);q=ceil(q,q);k=k>>1;}return p;
}
int main()
{ int n;while(~scanf("%d",&n),n){ if(n==1) printf("1\n");else if(n==2) printf("2\n");else if(n>=3){ a.s[0][0]=1;a.s[0][1]=0;a.s[0][2]=0;a.s[1][0]=0;a.s[1][1]=1;a.s[1][2]=0;a.s[2][0]=0;a.s[2][1]=0;a.s[2][2]=1;b.s[0][0]=0;b.s[0][1]=2;b.s[0][2]=0;b.s[1][0]=1;b.s[1][1]=1;b.s[1][2]=0;b.s[2][0]=0;b.s[2][1]=1;b.s[2][2]=1;n-=2;Node c=doit(n);L k=(c.s[0][1]+c.s[1][1]*2+c.s[2][1])%M;printf("%I64d\n",k);}}return 0;
}
这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=2842的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
