Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
A new variant of the COVID-19 virus has been detected in the country. This variant is called the 'omago' variant because once someone becomes infected with the variant, they will always be infected. The new variant is also very contagious. Scientists wonder how many days it will take for the virus to infect everyone in the country. There are n people in the country. Initially, m people are infected with the virus. Every day each infected person spreads the virus to k randomly chosen distinct people except himself. If the virus spreads to a non-infected person, they become infected at the beginning of the next day. An infected person will always be infected. Find the expected number of days before every person becomes infected.

A new variant of the COVID-19 virus has been detected in the country. This variant is called the 'omago' variant because once someone becomes infected with the variant, they will always be infected. The new variant is also very contagious. Scientists wonder how many days it will take for the virus to infect everyone in the country. There are n people in the country. Initially, m people are infected with the virus. Every day each infected person spreads the virus to k randomly chosen distinct people except himself. If the virus spreads to a non-infected person, they become infected at the beginning of the next day. An infected person will always be infected. Find the expected number of days before every person becomes infected.

Computer Networking: A Top-Down Approach (7th Edition)
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
See similar textbooks
icon
Related questions
Question
A new variant of the COVID-19 virus has been detected in the country. This variant is called the 'omago' variant because once someone becomes infected with the variant, they will always be infected. The new variant is also very contagious. Scientists wonder how many days it will take for the virus to infect everyone in the country. There are n people in the country. Initially, m people are infected with the virus. Every day each infected person spreads the virus to k randomly chosen distinct people except himself. If the virus spreads to a non-infected person, they become infected at the beginning of the next day. An infected person will always be infected. Find the expected number of days before every person becomes infected. Input The first line will contain a single integer T, the number of test cases. Each case is described by a single line containing three space-separated integers n, k, and m. Output For each case, print a single integer in a new line, the expected number of days before everyone becomes infected modulo 998244353. Formally, let M = 998244353. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are coprime integers and q is not divisible by M. You should output the integer equal to p-q¹ (mod M). In other words, output an integer x such that 0 < x < M and q-x = p (mod M) Constraints 1STS 11 1 ≤ n ≤ 400 • • 1 ≤k, m<n • n ≤ 100 for at least T-1 cases. Sample Input Output for Sample Input 332748120 1 For the first case, the expected number of days is 7/3, So the answer is 7-3-1 (mod 998244353) = 332748120. For the second case, initially 2 people are infected. On the first day, both persons will spread the virus to all other persons. Thus it will take only 1 day.
Transcribed Image Text:A new variant of the COVID-19 virus has been detected in the country. This variant is called the 'omago' variant because once someone becomes infected with the variant, they will always be infected. The new variant is also very contagious. Scientists wonder how many days it will take for the virus to infect everyone in the country. There are n people in the country. Initially, m people are infected with the virus. Every day each infected person spreads the virus to k randomly chosen distinct people except himself. If the virus spreads to a non-infected person, they become infected at the beginning of the next day. An infected person will always be infected. Find the expected number of days before every person becomes infected. Input The first line will contain a single integer T, the number of test cases. Each case is described by a single line containing three space-separated integers n, k, and m. Output For each case, print a single integer in a new line, the expected number of days before everyone becomes infected modulo 998244353. Formally, let M = 998244353. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are coprime integers and q is not divisible by M. You should output the integer equal to p-q¹ (mod M). In other words, output an integer x such that 0 < x < M and q-x = p (mod M) Constraints 1STS 11 1 ≤ n ≤ 400 • • 1 ≤k, m<n • n ≤ 100 for at least T-1 cases. Sample Input Output for Sample Input 332748120 1 For the first case, the expected number of days is 7/3, So the answer is 7-3-1 (mod 998244353) = 332748120. For the second case, initially 2 people are infected. On the first day, both persons will spread the virus to all other persons. Thus it will take only 1 day.
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS