首页 > 代码库 > HDU - 2842 Chinese Rings
HDU - 2842 Chinese Rings
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.
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个环那么要保证前n-2都取下,第n-1还在
思路:设取下第n个环的最短时间是f[n],那么要想取下第n个环,首先要取下前n-2个即:f[n-2]以及最后一个,所以是
f[n-2]+1, 还有一个第n-1个,要取下它首先要保证第n-2在,所以需要f[n-2](怎么取下来的怎么放上去),现在又要取第n-1个了, 综上所述:f[n] = 2*f[n-2] + f[n-1] + 1, 然后就是构造矩阵了:
不难推出来: | f[n] | | 1 2 1 | | f[n-2]|
| f[n-1] | = | 1 0 0 | * | f[n-1]|
| 1 | | 0 0 1 | | 1 |
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int maxn = 10; const int mod = 200907; int cnt; struct Matrix { int v[maxn][maxn]; Matrix() {} Matrix(int x) { init(); for (int i = 0; i < maxn; i++) v[i][i] = x; } void init() { memset(v, 0, sizeof(v)); } Matrix operator *(Matrix const &b) const { Matrix c; c.init(); for (int i = 0; i < cnt; i++) for (int j = 0; j < cnt; j++) for (int k = 0; k < cnt; k++) c.v[i][j] = (c.v[i][j] + (ll)v[i][k]*b.v[k][j]) % mod; return c; } Matrix operator ^(int b) { Matrix a = *this, res(1); while (b) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } } a, b, tmp; int main() { int n; while (scanf("%d", &n) != EOF && n != 0) { if (n < 3) { printf("%d\n", n); continue; } a.init(); cnt = 3; a.v[0][0] = a.v[0][2] = a.v[1][0] = a.v[2][2] = 1; a.v[0][1] = 2; tmp = a^(n-2); printf("%d\n", (tmp.v[0][0]*2 + tmp.v[0][1] + tmp.v[0][2]) % mod); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。