ICPC Russia Just the Last Digit

J. Just the Last Digit
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Jessie has recently started jogging and tracking the progress with a fitness band. There are n spectacular spots on a nearby hill. As running uphill is hard for an amateur jogger, Jessie is only going to run downhill. The spots have numbers from 1 to n, the higher the number is, the lower the spot is. Some pairs of spots are connected by trails, and for our purpose, we will only consider trails i→j going from a higher spot to a lower spot (i<j).

Jessie successfully finished some number of jogs, running through each possible sequence of spots, for which a trail between any two consecutive spots exists, exactly once. Now Jessie is planning to restore the map of all trails with the help of data collected by the fitness band. Unfortunately, the display on the band is small, and can only show the last digit of the number of jogs Jessie did between each pair of spots i and j where 1≤i<j≤n. Can you help Jessie restore the map of the hill given this data?

Input
The first line of the input contains an integer n — the number of spots on the hill (2≤n≤500). Next, n lines follow: the i-th line contains n characters ai,1,ai,2,…,ai,n. Character ai,j is the last digit of the number of different jogs made by Jessie starting at the i-th spot and ending at the j-th spot. For every i≥j, ai,j=0.

It is guaranteed that a solution always exists for the given input data.

Output
Print n lines, describing the map of the hill in the similar format: the i-th line should contain n characters, where j-th character is 1 if there is a trail from the i-th spot to the j-th spot, and 0 otherwise. For every i≥j, the j-th character in the i-th row must be 0.

Example
inputCopy
5
01113
00012
00001
00001
00000
outputCopy
01100
00011
00001
00001
00000

从后往前枚举每一个点。

比如当前看s到t的路径条数，那么只能通过s+1到t-1的所有点中转。如果最后和 g[s][t] 不相等，那么肯定s到t有直接的连线。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=510;
int n,g[N][N],res[N][N];
char a[N][N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	g[i][j]=a[i][j]-'0';
	for(int i=n-1;i>=1;i--){
		for(int j=i+1;j<=n;j++){
			int t=0;
			for(int k=i+1;k<j;k++)	t=(t+res[i][k]*g[k][j])%10;
			if(t!=a[i][j]-'0')	res[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)	cout<<res[i][j];puts("");
	}
	return 0;
}