M. Chat Group

Codeforces
IDCF10177M
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
It is said that a dormitory with 6 persons has 7 chat groups _^_^_. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups. Given N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be? The input starts with one line containing exactly one integer T which is the number of test cases. Each test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group. For each test case, output one line containing "_Case #x: y_" where _x_ is the test case number (starting from 1) and _y_ is the number of different chat groups modulo 1000000007. ## Input The input starts with one line containing exactly one integer T which is the number of test cases.Each test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group. 1 ≤ T ≤ 100. 1 ≤ N ≤ 109. 3 ≤ K ≤ 105. ## Output For each test case, output one line containing "_Case #x: y_" where _x_ is the test case number (starting from 1) and _y_ is the number of different chat groups modulo 1000000007. [samples]
**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ i \in \{1, \dots, T\} $, let $ N_i \in \mathbb{Z} $ be the number of persons, and $ K_i \in \mathbb{Z} $ be the minimum group size. **Constraints** 1. $ 1 \leq T \leq 1000 $ 2. For each test case: $ 1 \leq K_i \leq N_i \leq 10^9 $ **Objective** For each test case $ i $, compute the number of subsets of size at least $ K_i $ from $ N_i $ persons: $$ y_i = \sum_{j=K_i}^{N_i} \binom{N_i}{j} \mod 1000000007 $$
API Response (JSON)
{
  "problem": {
    "name": "M. Chat Group",
    "description": {
      "content": "It is said that a dormitory with 6 persons has 7 chat groups _^_^_. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups. Gi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10177M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It is said that a dormitory with 6 persons has 7 chat groups _^_^_. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups.\n\nGi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $, let $ N_i \\in \\mathbb{Z} $ be the number of persons, and $ K_i \\in \\mathbb{Z} $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments