POJ 1977 Odd Loving Bakers
Time Limit: 2000MS
Memory Limit: 30000K
Total Submissions: 1372
Accepted: 429
Description
There is a group of N bakers in the town of Utopia. These bakers hold a monthly celebration in which they award a prize to some of the luckier among themselves. These lucky guys are chosen as follows:
In the beginning there are some chalk marks on some of the bakers' houses. Each baker has a list of his/her favorite bakers. After each celebration each of the winners puts a chalk mark on the house of all the bakers in his/her favorite list. Before each celebration those bakers with an odd number of chalk marks on their house will be chosen as winners. As there will be a great prize for the winners of the t
th celebration, you are asked to find the number of its winners.
Input
The first line of the input contains a single integer X (1 <= X <= 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows:
The first line of each instance contains two integers n (the number of bakers) and t (the number of the celebration we want the winners of).
1 <= n <= 100
1 <= t <= 1,000,000,000
The next n lines of the instance each describe a baker. In each of these lines first comes the name of the baker (names are lower case strings of no more than 20 characters without spaces), then comes the number of chalk marks initially on the baker's house, then comes the number of bakers in this baker's favorite list, and after that come the names of the bakers in this baker's list.
Output
There should be one line per test case. For each test case write a line containing a single integer, the number of the winners of the t-th celebration.
Sample Input
2
3 2
bessie 2 3 bessie linda mary
mary 1 1 linda
linda 0 1 bessie
2 2
siavosh 1 2 siavosh mohammad
mohammad 1 0
Sample Output
2
0
Source
Tehran Sharif 2004 Preliminary
/* 우선 제목 입력에 따라 a[] 및 rel[][], a[i]는 1은 baker i 초기의 chalk 수를 홀수로 표시하고, 그렇지 않으면 짝수로 한다. rel[i][j]=1은 baker i가 baker j를 흠모하는 것을 나타낸다. 그러면 첫 번째 경축이 끝난 후의 위너 상태는 a[]* rel[]+ a[]= a[]* (rel[]+ I[]), I 단위 행렬, 같은 이치로 두 번째 후의 상태는 a[]* (rel[]+ I])^2,그래서 p회 후의 위너 상태는 a*(rel[][]+I[]]])^n이다.그래서 전체 문제는 행렬의 빠른 멱 연산으로 전환된다.행렬의 빠른 멱 연산과 대수 멱 연산은 매우 비슷하다. res=A^pmodk를 구하고 p를 2진법으로 전환한 다음에 낮은 위치에서 높은 위치로 계산한다. 예를 들어 p=10110이면 A^pmodk={(A^10)modk)*(A^100)modk)*(A^10000)modk}를 반복할 때 보조 행렬 expv로 기록(A^(2^i)modk를 할 수 있다. 위로 처리할 때마다 expv*=expv를 처리한다. 만약에 p의 현재 위치가 1이면res+=expvmodk,마지막res는 결과*/#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다. 아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다. UI 요소뿐만 아니라 원본 데이터 당 삭제합니다. 잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.