int A[logk][n][n], B[logk][n][n];

// A[x][i][j] = A^(2^x);
// B[x][i][j] = A^1 + A^2 + ... + A^(2^x);

一下是递推公式：

A[x+1] = A[x] * A[x];
B[x+1] = A[x] * B[x] + B[x];

S = A^1 + A^2 + .... + A^k
   
将 k 分解为 2^bi + 2^bi-1 + …… + 2^bj；
则 
S = (A^1 + A^2 + ... + A^(2^bi) ) + A^(2^bi) * (A^1 + A^2 + ... + A^(2^bi-1)) + A^(2^bi + 2^bi-1) * (A^1 + A^2 + ... + A^(2^bi-2) )  + ... + A^(2^bi + 2^bi-1 + ... + 2^bj+1) * (A^1 + A^2 + ... + A^(2^bj) ) 

= B[bi] + A[bi] * B[bi-1] + A[bi] * A[bi-1] * B[bi-2] + ... + A[bi] * A[bi-1] * ... * A[bj+1] * B[bj]  ;

Sample:

S = A + A^2 + ... + A^14

14 = 2^1 + 2^2 + 2^3

S = (A^1 + A^2) + A^2 * (A^1 + A^2 + A^3 + A^4) + A^2 * A^4 * (A^1 + A^2 + ... + A^(2^3))

= B[1] + A[1] * B[2] + A[1] * A[2] * B[3]

复杂度为 O(n^3 * logk)

• 我的输出跟sample不一样，ac (846) Pzjay 2009-11-30 23:56:47