n范围较大。考虑构造矩阵加速。先构造一个向量。[F[i-1] *(i-1)^0 .... F[i-1]*(i-1)^k F[i]*i^0 ... F[i]*i^k sum[i-1]] 其中sum[i] = A[i](k) + .... A[1](k)。
若要从该向量变换到[F[i] *(i)^0 .... F[i]*(i)^k F[i+1]*(i+1)^0 ... F[i+1]*(i+1)^k sum[i]]。变换矩阵分为4部分。
1.新向量中的Fi*i^0.... Fi*i^k 可以直接从上一级向量获得。
2.sum[i]=sum[i-1]+F[i]*i^k;
3.F(i+1)*(i+1)^k=(Fi+Fi-1)* f(i^k, i^(k-1)...i^0) = Fi * f(i^k, i^(k-1) .. i^0) + F(i-1) * g((i-1)^k, ... (i-1)^0);
这样新向量能由旧向量的线性变换得到，第3条式子里的系数预处理时计算就好。
例： k=3时，变换矩阵A如下:
0 0 0 0 1 0 0 0
0
0 0 0 0 0 1 0 0
0
0 0 0 0 0 0 1 0
0
0 0 0 0 0 0 0 1
0
1 0 0 0 1 0 0 0
0
2 1 0 0 1 1 0 0
0
4 4 1 0 1 2 1 0
0
8 12 6 1 1 3 3 1 0
0 0 0 0 0 0 0 1 1
得到变换矩阵后，用快速幂和矩阵乘法加速。得到A^(n-1). A^(n-1)*[F1*1^0; ... F1 * 1^k; F2*2^0; ...F2*2^k; sum[1]]可获取答案。
1 #include <iomanip> 2 #include <iostream> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 using namespace std; 7 8 const int M = 1000000007; 9 10 long long *vector[100]; 11 long long *matrix[100]; 12 long long *final[100]; 13 14 void mul(long long *a[100], long long *b[100], int x, int y, int z) { 15 long long *c[100]; 16 for (int i = 0; i < x; i++) { 17 c[i] = (long long *)malloc(sizeof(long long) * y); 18 for (int j = 0; j < y; j++) { 19 c[i][j] = 0; 20 } 21 } 22 for (int i = 0; i < x; i++) 23 for (int j = 0; j < y; j++) 24 for (int k = 0; k < z; k++) { 25 c[i][j] = (c[i][j] + a[i][k] * b[k][j] % M) % M; 26 } 27 for (int i = 0; i < x; i++) 28 for (int j = 0; j < y; j++) { 29 b[i][j] = c[i][j]; 30 } 31 } 32 33 void quick_mul(long long *final[100], long long *matrix[100], int x, long long n) { 34 if (n == 0) { 35 for (int i = 0; i < x; i++) 36 for (int j = 0; j < x; j++) { 37 final[i][j] = 0; 38 } 39 for (int i = 0; i < x; i++) { 40 final[i][i] = 1; 41 } 42 return; 43 } 44 quick_mul(final, matrix, x, n >> 1); 45 mul(final, final, x, x, x); 46 if (n % 2) { 47 mul(matrix, final, x, x, x); 48 } 49 } 50 51 int main() { 52 long long n; 53 int k; 54 cin >> n >> k; 55 int x = k + k + 3; 56 for (int i = 0; i < x; i++) { 57 matrix[i] = (long long *)malloc(sizeof(long long) * x); 58 final[i] = (long long *)malloc(sizeof(long long) * x); 59 vector[i] = (long long *)malloc(sizeof(long long)); 60 } 61 for (int i = 0; i <= k; i++) { 62 vector[i][0] = 1; 63 } 64 long long t = 1; 65 for (int i = k + 1; i < x - 1; i++) { 66 t = (t << 1) % M; 67 vector[i][0] = t; 68 } 69 vector[x - 1][0] = 1; 70 for (int i = 0; i < x; i++) 71 for (int j = 0; j < x; j++) { 72 matrix[i][j] = 0; 73 } 74 for (int i = 0; i <= k; i++) { 75 matrix[i][k + 1 + i] = 1; 76 } 77 for (int i = 0; i <= k; i++) { 78 int w = k + 1 + i; 79 matrix[w][k + 1] = 1; 80 matrix[w][k + 1 + i] = 1; 81 for (int j = 1; j < i; j++) { 82 int u = k + 1 + j; 83 matrix[w][u] = (matrix[w - 1][u] + matrix[w - 1][u - 1]) % M; 84 } 85 for (int j = 0; j <= i; j++) { 86 matrix[w][j] = matrix[w][j + k + 1]; 87 } 88 for (int j = 0; j < i; j++) { 89 for (int t = i - j - 1; t >= 0; t--) { 90 matrix[w][t] = (matrix[w][t] + matrix[w][i - j + k + 1] * matrix[w - j][t + k + 1] % M) % M; 91 } 92 } 93 } 94 matrix[x - 1][x - 2] = 1; 95 matrix[x - 1][x - 1] = 1; 96 quick_mul(final, matrix, x, n - 1); 97 mul(final, vector, x, 1, x); 98 cout << vector[x - 1][0] << endl; 99 return 0; 100 }
Codeforces Round 230 Div 1. C.Yet Another Number Sequence
原文：http://www.cnblogs.com/nilmo/p/3561783.html