HDU 2294 Pendant （DP+矩陣快速冪降維）

HDU 2294 Pendant （DP+矩陣快速冪降維）

ACM

題目地址：HDU 2294 Pendant

題意：
土豪給妹子做首飾，他有K種珍珠，每種N個，為了炫富，他每種珍珠都要用上。問他能做幾種長度[1,N]的首飾。

分析：
1 ≤ N ≤ 1,000,000,000簡直可怕。
首先想dp，很明顯可以想到：
dp[i][j] = (k-(j-1))*dp[i-1][j-1] + j*dp[i-1][j]（dp[i][j]表示長度為i的並且有j種珍珠的垂飾有多少個）
然後遇到N太大的話，得考慮優化，用矩陣快速冪轉移狀態簡直太神。
引用巨巨文：

由於N太大，所以把i看成“階段”，構造矩陣，通過矩陣快速轉移
設第i階段的一維數組(dp[i][0~j])狀態設為F，轉移矩陣為init（k+1階方陣） 則有：init * F = F';（F'為新狀態）
設答案 = gn = dp[1][k] + dp[2][k] + ... + dp[n][k] 所以有矩陣：

| 1 0...............0 1 |       |g0|        |g1'| 
| 0 1 0...............0 |       |f1|        |f1'| 
| 0 k-1 2.............0 |       |f2|        |f2'| 
| ..................... |   *   |..|    =   |..'| 
| 0...0 k-(j-1) j 0...0 |       |fj|        |fj'| 
| ..................... |       |..|        |..'| 
| 0...............0 1 k |       |fk|        |fk'| 

這個代碼的初始化：[g0, f1, f2, ..., fk] = {0, k, 0, ..., 0}

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2294.cpp
*  Create Date: 2014-08-03 16:03:27
*  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 = 31;	// max size of the matrix
const int MOD = 1234567891;

int ans[N];
int t, n, k;

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;
}

void init() {
	scanf("%d%d", &n, &k);
	a.n = b.n = c.n = k + 1;
	a.init(0);
	a.v[0][0] = a.v[0][k] = 1;
	repf (i, 1, k) {
		if (i > 1)
			a.v[i][i - 1] = k - i + 1;
		a.v[i][i] = i;
	}
	b.init(0);
	b.v[1][0] = k;
}

void solve() {
	c = a ^ n;
	c = c * b;
	printf("%lld\n", c.v[0][0]);
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		solve();
	}
	return 0;
}