程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2842 Chinese Rings (帶常數矩陣+矩陣快速冪)

HDU 2842 Chinese Rings (帶常數矩陣+矩陣快速冪)

編輯:C++入門知識

HDU 2842 Chinese Rings (帶常數矩陣+矩陣快速冪)


HDU 2842 Chinese Rings (帶常數矩陣+矩陣快速冪)

ACM

題目地址:HDU 2842 Chinese Rings

題意:
一種中國環,解開第k個環需要先解開前(k-2)個環,並留有第(k-1)環。問解開n環最少需要幾步。

分析:
設f(n)表示解開n環。
1. 由於游戲規則,解開n環不能一下子把n-1全解開了,否則第n個就沒法拿掉了。
2. 得先拿掉第n個:先完成f(n-2),然後再拿掉第n環。
3. 然後放回前(n-2),其實這也是f(n-2),因為是一個逆的過程。
4. 最後就變成完成f(n-1)了。

那f(n-1)呢?那是它自己的事了。。。
所以f(n) = f(n-2)+1 + f(n-2) + f(n-1)。
第一次遇到含有常數的式子,常數原來可以用的啊。

  1. | f[n] | | 1 2 1 | |f[n-2]|
  2. |f[n-1]| = | 1 0 0 | * |f[n-1]|
  3. | 1 | | 0 0 1 | | 1 |

代碼:

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2842.cpp
*  Create Date: 2014-08-03 22:22:57
*  Descripton:   
*/

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;

const int N = 31;
const int SIZE = 3;	// max size of the matrix
const int MOD = 200907;

struct Mat{
	int n;
	ll v[SIZE][SIZE];	// value of matrix

	Mat(int _n = SIZE) {
		n = _n;
		memset(v, 0, sizeof(v));
	}

	void init(ll _v) {
		memset(v, 0, sizeof(v));
		repf (i, 0, n - 1)
			v[i][i] = _v;
	}

	void output() {
		repf (i, 0, n - 1) {
			repf (j, 0, n - 1)
				printf("%lld ", v[i][j]);
			puts("");
		}
		puts("");
	}
} a, b, c;

Mat operator*(Mat a, Mat b) {
	Mat c(a.n);
	repf (i, 0, a.n - 1) {
		repf (j, 0, a.n - 1) {
			c.v[i][j] = 0;
			repf (k, 0, a.n - 1) {
				c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD;
				c.v[i][j] %= MOD;
			}
		}
	}
	return c;
}

Mat operator ^ (Mat a, ll k) {
	Mat c(a.n);
	c.init(1);
	while (k) {
		if (k&1) c = c * a;
		a = a * a;
		k >>= 1;
	}
	return c;
}

ll solve(int n) {
	if (n <= 2) {
		return n;
	}
	// init
	a.v[0][1] = 2;
	a.v[0][0] = a.v[0][2] = a.v[1][0] = a.v[2][2] = 1;
	b.v[0][0] = 2;
	b.v[1][0] = b.v[2][0] = 1;
	
	c = a ^ (n - 2);
	c = c * b;
	return c.v[0][0];
}

int main() {
	int n;
	while (~scanf("%d", &n) && n) {
		cout << solve(n) << endl;
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved