hdu 2842 Chinese Rings（矩阵递推）

hdu 2842 Chinese Rings（矩阵递推）

​​_ 1 _ 这样的情况是不能直接拿第3个环的。

第3个环应该是：

1.拿走第1个环

2.拿走第3个环

3.放回第1个环

4.拿走第2个环

5.拿走第1个环。

推广：

对于第N个环，全部拿完N个环的步数f(n)=f(n-2)+1+f(n-2)+f(n-1). 即先拿走前n-2个环，再拿走nth环，放回前n-2个环，处理剩余的n-1个环。f(n)=f(n-1)+2f(n-2)+1

哇哦，递推式中有一个调皮的常数。

整理递推矩阵：

#include #include using namespace std;const int mod=200907;typedef long long LL;struct matrix{ LL m[3][3];}I;matrix A={1,2,1,1,0,0,0,0,1};matrix multi(matrix a,matrix b){ matrix c; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ c.m[i][j]=0; for(int k=0;k<3;k++){ c.m[i][j]+=a.m[i][k]*b.m[k][j]; } c.m[i][j]%=mod; } } return c;}matrix power(int p){ matrix ans=I,temp=A; while(p){ if(p&1) ans=multi(ans,temp); temp=multi(temp,temp); p>>=1; } return ans;}int main(){ for(int i=0;i<3;i++) I.m[i][i]=1; int n; while(cin>>n&&n){ matrix ans=power(n-1); printf("%lld\n",(ans.m[0][0]+ans.m[0][2])%mod); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。