Amplitude Hackathon '23 Problem 6 - Journeys

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 5.0s
Memory limit: 1G

Problem types

Amplitude recently implemented journeys! This problem is inspired by journeys, but knowledge of how journeys works or what the product surfaces is not required to solve this problem.

Spenser is on a journey as CEO of Amplitude and is charting the future direction of the company. The company can be in one of N different states, and depending on Amplitude's current state, he can take certain actions to move Amplitude to a different state. Spenser's actions can never result in Amplitude returning to a previous state.

Spenser wants to know, for each possible pair of starting and ending state, how many distinct journeys there are that Amplitude can take to get between the starting state and ending state. Formally, we say that a sequence of states (s_1, \dots, s_K) is a journey between state s_1 and state s_K if and only if for every i where 1 \le i < K, there is an action that Spenser can take to move Amplitude directly from state s_i to state s_{i+1}.

Two journeys are different if some state appears in one journey but not in the other.

Constraints

1 \le N \le 500

If Spenser can take a single action to make Amplitude go from state i to state j, then i < j.

Subtask 1 [1 point]

1 \le N \le 10

Subtask 2 [1 point]

1 \le N \le 50

Subtask 3 [1 point]

No additional constraints.

Input Specification

The first line of input contains a single positive integer, N.

The next N lines each contain a binary string of length N. If the jth character of line i is a 1, then Spenser can move Amplitude directly from state i to state j. Otherwise, the jth character of line i is a 0.

Output Specification

Output N lines, each with N integers. Let f(i, j) be the number of journeys with starting state i and ending state j. The jth integer on the ith line should be the remainder when f(i, j) is divided by 998244353.

Sample Input 1

3
011
001
000

Sample Output 1

1 1 2
0 1 1
0 0 1

Sample Explanation 1

There are two journeys from state 1 to state 3: (1, 2, 3) and (1, 3).

There is one journey from state 1 to state 2: (1, 2).

There is one journey from state 2 to state 3: (2, 3).

There is always exactly one journey from a state to itself.

Sample Input 2

3
010
001
000

Sample Output 2

1 1 1
0 1 1
0 0 1

Sample Explanation 2

There is now only one journey from state 1 to state 3: (1, 2, 3).


Comments

There are no comments at the moment.