Colorful Spanning Trees

5

2 votes
determinant, Linear Algebra, Hard, Mathematics, counting, Approved, interpolation
Problem

You are give an graph with multiple edges and without loops. Each edge have one of 2 colors -- black or white.

For each i between 0 and \(n-1\), inclusive, find number of spanning trees with exactly i white edges and \(n - 1 - i\) black edges.

As answers can be large, print them modulo \(1,000,000,007\).

Input Format:
First line contain single integer n -- number of vertices in a graph.
Then two tables \(n \times n\) follows, separated by an empty line.
First table contains number of white edges between vertices, second black.

n
\(w_{11} \dots w_{1n}\)
\(\vdots\)
\(w_{n1} \dots w_{nn}\)

\(b_{11} \dots b_{1n}\)
\(\vdots\)
\(b_{n1} \dots b_{nn}\)

Output Format:
Output n space-separated numbers, i containing number of trees with i white and \(n - 1 - i\) black edges.

Constraints:
\(2 \leqslant n \leqslant 100\).
\(0 \leqslant w_{ij}, b_{ij} \leqslant 1,000,000,006\).
\( w_{ii} = b_{ii} = 0\).
\( w_{ij} = w_{ji}, b_{ij} = b_{ji} \).

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

.

Editor Image

?