I. Thanos's snap

Codeforces

IDCF10240I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The city of Diegopolis has been growing to the point of reaching exactly 5 million people (making it 74th most populated city in the world), but to Diego's surprise (Diego is the mayor of Diegopolis), Thanos is about to snap his fingers and reduce the universe's population in approximately half. Because of this Diego wants to know what is the probability that at least K of his people survive Thanos's snap, since this number can be quite small make sure you print it modulo $10^9 + 7$. You should assume that any person has exactly 50% chance of surviving Thanos's snap. A number $T$ $(1 < = T < = 10^5)$, the amount of test cases. Followed by $T$ lines, each line has an integer $K$ $(1 < = K < = 5000000)$. For each test case print a single integer $P$ $(0 < = P < 10^9 + 7)$, the probability that at least $K$ people survive Thano's snap. In the sample test case there is a 100% chance that at least 0 people survive while the chances of all 5 million Diegopolians surviving is $frac(1, 2^(5000000)) equiv 195206359 mod 10^9 + 7$. ## Input A number $T$ $(1 < = T < = 10^5)$, the amount of test cases.Followed by $T$ lines, each line has an integer $K$ $(1 < = K < = 5000000)$. ## Output For each test case print a single integer $P$ $(0 < = P < 10^9 + 7)$, the probability that at least $K$ people survive Thano's snap. [samples] ## Note In the sample test case there is a 100% chance that at least 0 people survive while the chances of all 5 million Diegopolians surviving is $frac(1, 2^(5000000)) equiv 195206359 mod 10^9 + 7$.

**Definitions** Let $ N = 5 \times 10^6 $. Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ K \in \mathbb{Z} $ satisfy $ 1 \le K \le N $. **Constraints** 1. $ 1 \le T \le 10^5 $ 2. $ 1 \le K \le N $ **Objective** For each test case, compute the probability that at least $ K $ people survive, where each of the $ N $ people survives independently with probability $ \frac{1}{2} $. Let $ X \sim \text{Binomial}(N, \frac{1}{2}) $. Compute: $$ P_K = \Pr(X \ge K) = \sum_{i=K}^{N} \binom{N}{i} \left(\frac{1}{2}\right)^N \mod (10^9 + 7) $$ Output $ P_K \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "I. Thanos's snap",
    "description": {
      "content": "The city of Diegopolis has been growing to the point of reaching exactly 5 million people (making it 74th most populated city in the world), but to Diego's surprise (Diego is the mayor of Diegopolis),",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10240I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The city of Diegopolis has been growing to the point of reaching exactly 5 million people (making it 74th most populated city in the world), but to Diego's surprise (Diego is the mayor of Diegopolis),...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N = 5 \\times 10^6 $.  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ K \\in \\mathbb{Z} $ satisfy $ 1 \\le K \\le N $.\n\n**Constraints**  \n1. $ 1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments