프로그램 명: coci_lubenica
제한시간: 1 초
Children in school are having fun instead of listening to the teacher. With their iPhone devices the
children throw watermelons at each other on the Facebook social site.
The game started when Goran threw one watermelon at each of his friends during the first class that
day. During subsequent classes, all children (including Goran) behaved like this:
- If they had been hit by an odd number of watermelons during the previous class, they threw
exactly one watermelon at each of their friends;
- If they had been hit by an even number of watermelons (including zero), then they hit each of
their friends with two watermelons.
The children are numbered 1 through N, Goran obviously being number 1. The friend relationships
between the children are also known.
Write a program that will calculate the total number of watermelons thrown after H classes.
입력
The first line contains two integers N and H (1 ≤ N ≤ 20, 1 ≤ H ≤ 1000000 000), the number of kids
and classes.
Each of the following N lines contains a string of N characters '0' or '1'. The character (A, B) in this
matrix is '1' if children A and B are friends.
No child will be their own friend. The input matrix will be symmetric.
출력
Output the number of watermelons after H classes.
입출력 예
input
4 1
0110
1001
1001
0110
output
2
input
4 2
0110
1001
1001
0110
output
14
input
5 3
01000
10110
01000
01001
00010
output
26
EXAMPLES
In the second example, Goran throws two watermelons during the first class. During the second
class, children 1 and 4 each throw two watermelons at 2 and 3 each, while 2 and 3 throw one
watermelon at 1 and 4. A total of 12 watermelons is thrown during the second class.
출처: coci 2008/2009 contest5 4/6
[질/답]
[제출 현황]
[푼 후(0)]