HDU2842 Chinese Rings 带常数矩阵快速幂+思维

常数矩阵快速幂+思维"/>

HDU2842 Chinese Rings 带常数矩阵快速幂+思维

先贴大佬博客Orz：

这道题有几点很巧妙：

1.拿掉第n个：先完成f(n-2)，再拿掉第n环；然后放回前(n-2)（其实这也是f(n-2)），再加上f(n-1)

最终得到f(n)=f(n-1)+2*f(n-2)+1即为递推式。另：初始化f(1)=1，f(2)=2

2.矩阵快速幂中，遇到含有常数的式子，可以把A矩阵扩展为3*3的矩阵。

即最终得到下式：

                          |  f(n)   |     | 1  2  1 |    | f(n-1) |

                          | f(n-1) | =  | 1  0  0 | * | f(n-2) |

                          |    1     |     | 0  0  1 |   |    1     |

中间的即为A矩阵，接下来用矩阵快速幂的板子就行了。附上AC代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)const int MOD=200907;
ll n;
typedef struct
{ll a[3][3];//矩阵大小
}mat;
mat c,res;mat mul(mat x,mat y,int n)
{mat cnt;memset(cnt.a,0,sizeof(cnt.a));for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)cnt.a[i][j]+=x.a[i][k]*y.a[k][j]%MOD;return cnt;
}
void pow()
{c.a[0][0]=1;c.a[0][1]=2;c.a[0][2]=1;c.a[1][0]=1;c.a[1][1]=0;c.a[1][2]=0;c.a[2][0]=0;c.a[2][1]=0;c.a[2][2]=1;memcpy(res.a,c.a,sizeof(c.a));n-=3;while(n>0){if(n&1)res=mul(res,c,3);c=mul(c,c,3);n=(n>>1);}
}
int main()
{while(cin>>n){if(n==0)break;else if(n==1)cout<<"1"<<endl;else if(n==2)cout<<"2"<<endl;else{pow();cout<<(res.a[0][0]*2+res.a[0][1]+res.a[0][2])%MOD<<endl;}}return 0;
}