[HDU5015]233 Matrix
试题描述
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a0,1 = 233,a0,2 = 2333,a0,3 = 23333...) Besides, in 233 matrix, we got ai,j = ai-1,j +ai,j-1( i,j ≠ 0). Now you have known a1,0,a2,0,...,an,0, could you tell me an,m in the 233 matrix?
输入
There are multiple test cases. Please process till EOF.
输出
For each case, output an,m mod 10000007
输入示例
1 1 1 2 2 0 0 3 7 23 47 16
输出示例
234 2799 72937
数据规模及约定
见“输入”
题解
懒得翻译了，不难看懂（毕竟我也是英语渣）。
发现 n 很小，但是 m 必须在外面套一个 log，所以应该想到矩阵快速幂优化递推式。
第 0 行的 233 们可以有递推式 f(i) = f(i-1) * 10 + 3，其中 f(1) = 233.
第 1 行的则有 g(i) = g(i-1) + f(i)，其中g(1) = f(1) + a1,0.（a 为题目描述中的矩阵）
第 2 行的则有 h(i) = h(i-1) + g(i)，其中h(1) = g(1) + a2,0.
…
有规律了吧。。。
#include <iostream>
using namespace std;
#define maxn 15
#define MOD 10000007
#define LL long long
struct Matrix {
int n, m, A[maxn][maxn];
Matrix operator * (const Matrix& t) const {
Matrix ans; ans.n = t.n; ans.m = m;
for(int i = 1; i <= ans.n; i++)
for(int j = 1; j <= ans.m; j++) {
ans.A[i][j] = 0;
for(int k = 1; k <= n; k++) {
ans.A[i][j] += (int)(((LL)t.A[i][k] * A[k][j]) % MOD);
if(ans.A[i][j] > MOD) ans.A[i][j] -= MOD;
}
}
return ans;
}
} base, sol;
Matrix Pow(Matrix a, int x) {
Matrix t = a, ans = a; x--;
while(x) {
if(x & 1) ans = ans * t;
x >>= 1; t = t * t;
}
return ans;
}
int A[maxn];
int main() {
int n, m;
while(scanf("%d%d", &n, &m) == 2) {
for(int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
if(A[i] > MOD) A[i] %= MOD;
}
base.n = n + 2; base.m = 1;
sol.n = sol.m = n + 2;
base.A[n+2][1] = 1;
int sum = 233;
for(int i = n + 1; i; i--) {
base.A[i][1] = sum;
sum += A[n-i+2];
if(sum > MOD) sum -= MOD;
}
for(int i = 1; i <= n + 1; i++) {
for(int j = 1; j <= n; j++) if(j < i) sol.A[i][j] = 0;
else sol.A[i][j] = 1;
sol.A[i][n+1] = 10; sol.A[i][n+2] = 3;
}
for(int i = 1; i <= n + 1; i++) sol.A[n+2][i] = 0; sol.A[n+2][n+2] = 1;
if(m > 1) base = base * Pow(sol, m-1);
printf("%d\n", base.A[1][1]);
}
return 0;
}
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/5492713.html