2014
02-17

# Chinese Rings

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.

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".

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".

1
4
0

1
10

= f(n-2)+1+ f(n-2)+f(n-1),即f(n) = 2*f(n-2)+f(n-1)+1；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
#define mod 200907
int n;
struct node
{
__int64 map[3][3];
}unit,s;
node Mul(node a,node b)
{
node c;
int i,j,k;
for(i = 0; i < 3; i ++)
for(j = 0; j < 3; j ++)
{
c.map[i][j] = 0;
for(k = 0; k < 3; k ++)
c.map[i][j] += (a.map[i][k]*b.map[k][j])%mod;
c.map[i][j] %= mod;
}
return c;
}
void Matrix()
{
while(n)
{
if(n&1) unit = Mul(unit,s);
n >>= 1;
s = Mul(s,s);
}
}
int main()
{
int i,f[3] = {1,1,2};
while(scanf("%d",&n),n)
{
if(n <= 2)
{
printf("%d\n",f[n]);
continue;
}
memset(s.map,0,sizeof(s.map));
s.map[0][0] = 1; s.map[0][1] = 2; s.map[0][2] = 1;
s.map[1][0] = 1; s.map[2][2] = 1;
memset(unit.map,0,sizeof(unit.map));
for(i = 0; i < 3; i ++)
unit.map[i][i] = 1;
n -= 2;
Matrix();
__int64 ans = 0;
for(i = 0; i < 3; i ++)
ans += unit.map[0][i]*f[2-i], ans %= mod;
printf("%I64d\n",ans);
}
return 0;
}

1. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。