2080. GameOnAGraph

单点时限: 5.0 sec

内存限制: 256 MB

We have an undirected graph where each vertex is either black or white and has a mark, which is a non-negative integer. There are no edges that connect vertices of the same color. We are going to play a game with this graph. The rules are simple:

  1. White and black alternate turns. The first turn is white.

  2. During a white turn, we set the mark of each black vertex equal to the sum of the marks of all its neighbors. The marks of the white vertices remain unchanged.

  3. During a black turn, we set the mark of each white vertex equal to the sum of the marks of all its neighbors. The marks of the black vertices remain unchanged.

You are to find the marks of all vertices after N turns.

输入格式

You are given a vector adj where the j-th character of the i-th element is ‘1’ (one) if there is an edge between vertices i and j, and ‘0’ (zero) otherwise. You are given the coloring of the graph in the string colors, the i-th element of which is the color of the i-th vertex. ‘W’ denotes white and ‘B’ denotes black. The initial marks are given in the string marks, the i-th element of which is a digit representing the initial mark of the i-th vertex.

输出格式

output a vector where the i-th element is the mark of the i-th vertex modulo 10^9+7 after N turns.

样例

Input
4
0110
1000
1000
0000
WBBW
1000
1
Output
1
1
1
0
Detail:
In this case there is only one turn, so both black vertices get their marks from the first white vertex. The marks of the white vertices remain unchanged.

1 人解决,5 人已尝试。

1 份提交通过,共有 18 份提交。

9.9 EMB 奖励。

创建: 11 年,11 月前.

修改: 2 年,6 月前.

最后提交: 9 年,2 月前.

来源: TC

题目标签