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