题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2842
题目大意：棒子上套环。第i个环能拿下的条件是：第i-1个环在棒子上，前i-2个环不在棒子上。每个环可以取下或放上，cost=1。求最小cost。MOD 200907。
解题思路：
递推公式
题目意思非常无聊，感觉是YY的。
设$dp[i]$为取第i个环时的总cost。
$dp[1]=1$，$dp[2]=2$，前两个环取下是没有条件要求的。
从i=3开始，由于条件对最后的环限制最大，所以从最后一个环开始取。
$p[3]=5$（先取下第一个环，然后第三个环，然后放上第一个环，然后取下第二个环，然后取下第一个环)
$dp[4]=10$（规律是：取i环花费1，依赖花费$dp[i-1]$、$2*dp[i-2]$)
所以$dp[i]=dp[i-1]+2*dp[i-2]+1$
矩阵快速幂
任何递推数列都能构造矩阵求解，有N个参数的通项公式，至少需要构造$1*N$的矩阵
考虑到矩阵乘法的维数限制$[N,M]*[M,P]$，通常构造成$N*N$的矩阵。
构造方法就是按矩阵乘法的特性，先构造出幂矩阵第一列，然后YY出剩余列。
本题构造如下：
$\begin{bmatrix}f2 & f1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix}\begin{bmatrix}1 & 1&0 \\ 2 & 0&0 \\ 1& 0 &1 \end{bmatrix}=\begin{bmatrix}f3 & f2&1 \\
0 & 0&0 \\ 0& 0 &0\end{bmatrix}$
特判n=1、n=2，从n=3开始，幂(n-2)次，乘以基础f2、f1的矩阵。
代码
#include "cstdio"
#include "cstring"
#define LL long long
#define mod 200907
#define K 3
struct Matrix
{
LL mat[K][K];
Matrix() {memset(mat,,sizeof(mat));}
Matrix(LL *val)
{
int idx=;
for(int i=;i<K;i++)
for(int j=;j<K;j++)
mat[i][j]=val[idx++];
}
};
Matrix operator * (Matrix a,Matrix b)
{
Matrix ret;
for(int i=;i<K;i++)
for(int j=;j<K;j++)
{
ret.mat[i][j]=;
for(int k=;k<K;k++)
ret.mat[i][j]+=((a.mat[i][k]*b.mat[k][j])%mod);
}
return ret;
}
Matrix operator ^ (Matrix a,int n)
{
Matrix ret,base=a;
for(int i=;i<K;i++) ret.mat[i][i]=;
while(n)
{
if(n&) ret=ret*base;
base=base*base;
n>>=;
}
return ret;
}
int main()
{
//freopen("in.txt","r",stdin);
LL n;
while(scanf("%I64d",&n)&&n)
{
if(n==) printf("1\n");
else if(n==) printf("2\n");
else
{
LL bval[]={,,,,,,,,};
LL pval[]={,,,,,,,,};
Matrix Base(bval),Pow(pval),ans=Pow^(n-);
ans=Base*ans;
printf("%I64d\n",ans.mat[][]%mod);
}
}
}