矩阵连乘

题目描述:

ljc很无聊，于是找了n个矩阵，让你帮他算出它们的乘积。

 

输入格式:

有多组数据。 对于每组数据，第一行一个整数n，表示有n个矩阵。 第二行有n+1个由空格隔开的整数a_iai​ ，表示矩阵的大小，第i个矩阵的大小为a_i \times a_{i+1}ai​×ai+1​ 。 接下来有n个矩阵。 n=0时输入结束。详见样例。

输出格式:

对于每一个数据，输出Case #数据编号:，后面跟着一个矩阵。因为结果可能很大，你只要输出每个数模10003的结果。每一个数据用空行隔开。详见样例。

样例输入:

2
3 2 3
1 1
1 1
1 1
1 1 1
1 1 1
4
1 2 3 4 5
3 5
1 3 5
2 4 5
1 5 2 6
4 2 5 1
6 3 2 6
1 5 4 7 3
3 1 4 7 3
1 3 2 8 5
2 7 4 6 5
0

样例输出:

Case #1:
2 2 2
2 2 2
2 2 2

Case #2:
2043 5270 4338 8374 4826

提示:

n≤100,a_i​≤400 请放心，你只要用最优的方法，就不会TLE。update：假设n*m的矩阵和m*k的矩阵相乘，运算量为n*m*k，则若使用总运算量最小的运算顺序，每个Case中总运算量不超过1e7，共不超过3个Case。

你认为是dp？你认为是暴力？

时间限制: 3000ms
空间限制: 256MB

---

来源: by ljc