http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=909
Given an n×n matrix A and a 3×3 matrix K. These two matrices are very special : they are both non-negative matrices and the sum of all elements in matrix K is 1 (In order to avoid floating-point error, we will give matrix K in a special way in input).
Now we define a function C(A,K), the value of C(A,K) is also a n×n matrix and it is calculated below(we use C to abbreviate C(A,K)):
Cx,y=∑min(n−x+1,3)i=1∑min(n−y+1,3)j=1 Ax+i−1,y+j−1Ki,j
Now we define Cm(A,K)=C(Cm−1(A,K),K) and C1(A,K)=C(A,K), Kanade wants to know limt→∞Ct(A,K)
It's guaranteed that the answer exists and is an integer matrix.
The first line has one integer T.
Then for every test case:
The first line has one integer n.
Then there are n lines and each line has n non negative integers. The j-th integer of the i-th row denotes Ai,j
Then there are 3 lines and each line has 3 non negative integers. The j-th integer of the i-th row denotes K′i,j
Then K could be derived from K′ by the following formula:
1≤T≤100
3≤n≤50
0≤Ai,j≤1000
0≤K′i,j≤1000
∑3x=1∑3y=1K′x,y>0
Sample Output
题意：
定义一个函数C，参数为两个矩阵A和K，其中A是n*n矩阵，K是3*3矩阵，K是一个分数矩阵，Ki,j=K'i,j / ∑K'i,j，其中K‘是输入的整数矩阵，这意味着∑Ki,j=1
C的值由图里的公式求得
问对于同一个K，拿C套娃无穷次得到的矩阵
理解：
对于K矩阵，只要不是该矩阵只有一个数不为0，矩阵的每个元素值就都小于1;
Ax+i−1,y+j−1 × Ki,j ，无限套娃以后K的元素如果小于一结果就是0;
根据公式可以看出，超出A的部分直接被丢弃了;
如果K不满足只有左上角不为0的条件，那么结果就是全0，否则结果是A原矩阵，例如：
1 2 3 4 0 1 0
1 2 3 4 与 0 0 0 ，乘第一次会变成：
1 2 3 4 0 0 0
1 2 3 4
2 3 4 0
2 3 4 0 ，多乘几次就会全变为0,
2 3 4 0
2 3 4 0
而如果只有左上角不为0，每乘一次就是本身，无限次自然也不会变。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,a[1100][1100],b[10][10]; 5 int main(){ 6 int T; cin>>T; 7 for(int t=1;t<=T;++t){ 8 scanf("%d",&n); 9 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j) 10 scanf("%d",&a[i][j]); 11 int cnt=0; 12 for(int i=1;i<=3;++i)for(int j=1;j<=3;++j){ 13 scanf("%d",&b[i][j]); 14 if(b[i][j]) ++cnt; 15 } 16 if(cnt==1 && b[1][1]){ 17 for(int i=1;i<=n;++i){ 18 for(int j=1;j<=n;++j){ 19 printf("%d",a[i][j]); 20 if(j!=n) printf(" "); 21 } 22 printf(" "); 23 } 24 } 25 else{ 26 for(int i=1;i<=n;++i){ 27 for(int j=1;j<=n;++j){ 28 printf("0"); 29 if(j!=n) printf(" "); 30 } 31 printf(" "); 32 } 33 } 34 } 35 return 0; 36 }