题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2842
题目:
Problem Description
Dumbear likes to play the Chinese Rings (Baguenaudier). It's a game played with nine rings on a bar. The rules of this game are very simple: At first, the nine rings are all on the bar.
The first ring can be taken off or taken on with one step.
If the first k rings are all off and the (k + 1)th ring is on, then the (k + 2)th ring can be taken off or taken on with one step. (0 k 7)
Now consider a game with N (N 1,000,000,000) rings on a bar, Dumbear wants to make all the rings off the bar with least steps. But Dumbear is very dumb, so he wants you to help him.
Input
Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number "0".
Output
For each line, output an integer S indicates the least steps. For the integers may be very large, output S mod 200907.
- Sample Input
- 1 4 0
- Sample Output
- 1 10
题意: 给你个 n 连环 (就是平时玩的九连环类的益智玩具, 还不知道的就请自行百度一下啦......), 问最少要操作多少次才能把所有的环取下来~
思路: 个人认为这是要靠经验来, 没玩过的可能不知道该怎样取才能把所有的环都取下来. 第 n 项与前几项的关系是 f(n)=f(n-1)+2*f(n-2) + 1, 解释一下这个递推公式就是你要取下第 n 个的话得先把 1~n-2 都取下来 (第一个 f(n-2)), 第 n-1 个挂在上面, 然后把第 n 个取下来 (递推公式中 1 的由来), 然后再把 1~n-2 全部挂上去 (第二个 f(n-2)), 然后就是把第 n-1 取下去 (f(n-1)). 因为就可以构造出矩阵了, f[0] = 2, f[1] = 1, f[2] = 1;
- a[0][0] = 1, a[0][1] = 1, a[0][2] = 0;
- a[1][0] = 2, a[1][1] = 0, a[1][2] = 0;
- a[2][0] = 1, a[2][1] = 0, a[2][2] = 1.
代码实现如下:
- #include <cstdio>
- #include <cstring>
- typedef long long ll;
- const int mod = 200907;
- int n;
- int f[3], a[3][3];
- void mul(int f[3], int a[3][3]) {
- int c[3];
- memset(c, 0, sizeof(c));
- for(int i = 0; i <3; i++) {
- for(int j = 0; j < 3; j++) {
- c[i] = (c[i] + (ll) f[j] * a[j][i]) % mod;
- }
- }
- memcpy(f, c, sizeof(c));
- }
- void mulself(int a[3][3]) {
- int c[3][3];
- memset(c, 0, sizeof(c));
- for(int i = 0; i < 3; i++) {
- for(int j = 0; j < 3; j++) {
- for(int k = 0; k < 3; k++) {
- c[i][j] = (c[i][j] + (ll) a[i][k] * a[k][j]) % mod;
- }
- }
- }
- memcpy(a, c, sizeof(c));
- }
- int main() {
- while(~scanf("%d", &n) && n) {
- if(n == 1) {
- printf("1\n");
- continue;
- }
- if(n == 2) {
- printf("2\n");
- continue;
- }
- f[0] = 2, f[1] = 1, f[2] = 1;
- a[0][0] = 1, a[0][1] = 1, a[0][2] = 0;
- a[1][0] = 2, a[1][1] = 0, a[1][2] = 0;
- a[2][0] = 1, a[2][1] = 0, a[2][2] = 1;
- n = n - 2;
- for(; n; n>>= 1) {
- if(n & 1) mul(f, a);
- mulself(a);
- }
- printf("%d\n", f[0] % mod);
- }
- return 0;
- }
- Chinese Rings (九连环 + 矩阵快速幂)
来源: http://www.bubuko.com/infodetail-2580688.html