Problem H
Chatter
Joseph and his friends just love to chat online. Sometimes they just chat with random people they don’t even know, because it’s interesting to meet new people. When Joseph has dozens or hundreds of chat windows open, he sometimes wonders about who the people he’s chatting with are chatting with, and so on. He may be directly chatting with $10$ people, who are themselves chatting with $10$ other people each (that he’s not chatting with), giving Joseph over $100$ people who are $1$ or $2$ chats away. That is, he is either directly chatting to them, or he could send them a message through one of the people he’s chatting with. He wonders how many people are connected via chat in the group he’s in, especially if he considers people three chats away, four, etc.
He has asked you to write a program to determine how large are the groups of chatters being used on a server he runs. The chat server keeps track of all the people who are currently chatting with other people. Each day a bunch of people log in to the server, and then start randomly chatting with other people also logged in. Joseph wants your program to tell him the number of unique chat groups there are (people connected by chats), and how large each group is. We’ll also assume that once two people start chatting, they don’t stop until the server kicks everyone off at the end of the day.
Let the people logged on to the server be numbered $0$ to $n-1$. Each day, initially no one is chatting with anyone else. Then people make connections to chat with others, which we will simulate as follows.
-
Repeat $n$ times:
-
Choose $x$ as a random integer modulus $n$.
-
Choose $y$ as a random integer modulus $n$.
-
If $x = y$, choose $x$ and $y$ again randomly.
-
Start a chat between person $x$ and person $y$, if they are not already chatting.
-
Each time a random value $r$ is needed (including the first time), it is calculated as
\[ r \leftarrow (r \times a + b) \% c \]for given parameters $a$, $b$, $c$, and beginning with a seed value for $r$.
Input
Input has descriptions of up to $1\, 000$ days on the chat server, one day per line. Each line contains five integers $n~ r~ a~ b~ c$. The value $2 \le n \le 10\, 000$ represents both the number of people logged into the chat server and the number of chat connections to make in the simulation, $0 \le r \le 10\, 000$ is the random number seed used to connect users, and $1 \le a, b \le 10\, 000$ and $2 \le c \le 50\, 000$ are parameters for the random number generator. Input ends at end of file.
Output
For each day, output a line with the number of groups that are connected at the end of the day. Then list the size of each group, sorted from largest to smallest. If multiple groups have the same size, list the group size only once, followed by an ‘x’ and then the number of times that group occurs.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 5 1 2 200 100 311 523 39 101 |
6 5 1x5 50 3 2x48 1 |
