## Counting Paths

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type

Given a graph as an adjacency matrix, count the total number of paths of length .
The paths do not have to be simple.

#### Input Specification

Two integers, and .
An adjacency matrix, rows of numbers.

#### Output Specification

The number of different paths of length .

#### Sample Input

3 1
0 1 1
1 0 1
1 1 0

#### Sample Output

6

Note from admin: the test data for this problem is, in particular, erroneous. In certain cases, the answer is too large to be contained in a 32-bit signed integer. However, you should not move to larger data types, and should instead use this type (int in C/C++, longint in Pascal) to store the answer and "allow it to overflow" when necessary. Be cautious in other languages where 32-bit signed integers are not the primarily used type.