题目链接：?space=1&num=1507
Often, when a decision about investing in a new business must be taken, a New Russian has to estimate quickly whether a certain project will be a success or not. Leading economists have recently discovered a new algorithm for forecasting the success of a project.
First, one has to form ann×nmatrix of risks. Let us denote this matrix byA. Then, in order to take into account the interdependencies of the parameters inside the matrix, the matrix
must be computed. If at least one of the elements of the matrixBis zero, then there is a considerable probability that the project will fail. Otherwise, if there are no zero elements in the matrixB, the new business will grow and flourish.
Help New Russians to make use of this algorithm. Your task is to write a program that determines the probability of the success of a project given the matrix of its risks.
Input
The first line of the input contains the dimensionnof the matrixA(2 ≤n≤ 50). Each of the nextnlines containsnnumbers that forms the matrixA. Each element is a whole number in the range from 0 to 100.
Output
Output "No" if there is at least one zero element in the matrixB(so it is better not to invest in the new business). Otherwise, output "Yes".
Samples
inputoutput
20 715 30Yes
3100 35 400 22 010 11 0No
PS:
正解是用bool把相乘的结果中不为零的用true代替，不然会爆！
而我是把n*(n-1) 到n*(n+1)的幂 转化为从1开始！
代码如下：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define LL __int64struct Matrix{LL m[51][51];} I,A,B,T, ANS;LL a,n, mod;int ssize;Matrix Mul(Matrix a,Matrix b){int i, j, k;Matrix c;for (i = 1; i <= ssize; i++){for(j = 1; j <= ssize; j++){c.m[i][j]=0;for(k = 1; k <= ssize; k++){c.m[i][j]+=(a.m[i][k]*b.m[k][j]);//c.m[i][j]%=mod;}}}return c;}Matrix quickpagow(int n){Matrix m = A, b = I;while(n){if(n & 1)b = Mul(b,m);n = n >> 1;m = Mul(m,m);}return b;}void sum(Matrix T){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){ANS.m[i][j] += T.m[i][j];}}}int judge(Matrix ANS){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(ANS.m[i][j] == 0){return 1;}}}return 0;}int main(){LL c;while(~scanf("%I64d",&n)){ssize = n;memset(I.m,0,sizeof(I.m));memset(A.m,0,sizeof(A.m));memset(B.m,0,sizeof(B.m));memset(ANS.m,0,sizeof(ANS.m));for(int i = 1; i <= ssize; i++){//单位矩阵I.m[i][i]=1;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){scanf("%d",&A.m[i][j]);}}Matrix b = I;int beg = n*(n-1);int end = n*(n+1);int flag = 0;//T = I;//T = quickpagow(beg);//I = T;for(int i = beg; i <= end; i++){T = quickpagow(1);I = T;//T = Mul(T,A);sum(T);}flag = judge(ANS);if(flag){printf("No\n");}else{printf("Yes\n");}}return 0;}/*20 715 303100 35 400 22 010 11 0*/
这是队友的：#include<stdio.h>#include<string.h>struct Matrix{int m[51][51];};struct Matrix I,s;int n,kmod;Matrix Mul(Matrix a,Matrix b){Matrix c;int i,j,k;for(i=0; i<n; i++){for(j=0; j<n; j++){c.m[i][j]=0;for(k=0; k<n; k++){c.m[i][j]+=(a.m[i][k]*b.m[k][j]);}if(c.m[i][j]>0) c.m[i][j]=1;else c.m[i][j]=0;}}return c;}Matrix Add(Matrix a,Matrix b){Matrix c;int i,j;for(i=0; i<n; i++){for(j=0; j<n; j++){c.m[i][j]=(a.m[i][j]+b.m[i][j]);if(c.m[i][j]>0) c.m[i][j]=1;else c.m[i][j]=0;}}return c;}Matrix Quickpow(Matrix a,int n){Matrix m,b;m=a,b=I;while(n){if(n%2)b=Mul(b,m);n/=2;m=Mul(m,m);}return b;}int main(){int i,j;int k;while(scanf("%d",&n)!=EOF){Matrix ans;memset(I.m,0,sizeof I.m);memset(ans.m,0,sizeof ans.m);for(i=0; i<n; i++)I.m[i][i]=1;for(i=0; i<n; i++){for(j=0; j<n; j++){scanf("%d",&s.m[i][j]);if(s.m[i][j]>0) s.m[i][j]=1;else s.m[i][j]=0;}}for(i=n*(n-1); i<=n*(n+1); i++)ans=Add(ans,Quickpow(s,i));int flag=1;for(i=0; i<n; i++){for(j=0; j<n; j++){if(ans.m[i][j]==0)flag=0;}}if(flag) puts("Yes");else puts("No");}return 0;}
，人生就像是一场旅行，遇到的既有感人的，
