网站的程序和数据库怎么做,网站备案免费吗,为什么要做网站首页设计,网站如何做IPV6支持职务地址#xff1a;HDU 2842 这个游戏是一个九连环的游戏。 如果当前要卸下前n个环。由于要满足前n-2个都卸下#xff0c;所以要先把前n-2个卸下。须要f(n-2)次。然后把第n个卸下须要1次#xff0c;然后这时候要卸下第n-1个。然后此时前n-2个都已经被卸下了。这时候把前n-2… 职务地址HDU 2842 这个游戏是一个九连环的游戏。 如果当前要卸下前n个环。由于要满足前n-2个都卸下所以要先把前n-2个卸下。须要f(n-2)次。然后把第n个卸下须要1次然后这时候要卸下第n-1个。然后此时前n-2个都已经被卸下了。这时候把前n-2个都卸下与都装上所需的次数是一样的。由于卸下与装上的规则是一样的。所以又须要f(n-2)次。这时候前n-1个都在上面卸下前n-1个须要f(n-1)次。 所以。总共须要2*f(n-2)f(n-1)1次。 然后构造例如以下矩阵。 1,2,1 1,0,0 0,0,1 * f(n-1) f(n-2) 1 f(n) f(n-1) 1; 然后用矩阵高速幂求解。 代码例如以下 #include iostream
#include cstdio
#include string
#include cstring
#include stdlib.h
#include math.h
#include ctype.h
#include queue
#include map
#include set
#include algorithmusing namespace std;
#define LL __int64
const int mod200907;
struct matrix
{LL ma[4][4];
}init, res;
matrix Mult(matrix x, matrix y)
{matrix tmp;int i, j, k;for(i0;i3;i){for(j0;j3;j){tmp.ma[i][j]0;for(k0;k3;k){tmp.ma[i][j](tmp.ma[i][j]x.ma[i][k]*y.ma[k][j])%mod;}}}return tmp;
}
matrix Pow(matrix x, int k)
{matrix tmp;int i, j;for(i0;i3;i) for(j0;j3;j) tmp.ma[i][j](ij);while(k){if(k1) tmpMult(tmp,x);xMult(x,x);k1;}return tmp;
}
int main()
{int k, i, j;while(scanf(%d,k)!EOFk){if(k1){printf(1\n);continue ;}init.ma[0][0]1;init.ma[0][1]2;init.ma[0][2]1;init.ma[1][0]1;init.ma[1][1]0;init.ma[1][2]0;init.ma[2][0]0;init.ma[2][1]0;init.ma[2][2]1;resPow(init,k-2);LL ans;ans(2*res.ma[0][0]res.ma[0][1]res.ma[0][2])%mod;printf(%I64d\n,ans);}return 0;
}版权声明本文博主原创文章博客未经同意不得转载。 转载于:https://www.cnblogs.com/gcczhongduan/p/4840616.html
