O. April Fools' Problem (hard)

Codeforces

IDCF802O

Time10000ms

Memory256MB

Difficulty—

binary searchdata structuresflows

English · Original

Chinese · Translation

Formal · Original

The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan... ## Input Same as the medium version, but the limits have changed: 1 ≤ _k_ ≤ _n_ ≤ 500 000. ## Output Same as the medium version. [samples]

HC#cf_span[2] 的计划相当遥远：例如，我们距离 HC#cf_span[2] 3387 还有 50 多万天，因此我们计划在该版本中准备几十万个问题（我们希望编程竞赛会变得异常流行）。土拨鼠们需要开始工作，它们需要一个良好的计划... 与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。与中等版本相同。 ## Input 与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。 ## Output 与中等版本相同。 [samples]

Given integers $ n $ and $ k $ such that $ 1 \leq k \leq n \leq 500{,}000 $, compute the number of ways to choose $ k $ distinct elements from a set of $ n $ elements, modulo $ 10^9 + 7 $. That is, compute $ \binom{n}{k} \mod (10^9 + 7) $.

Samples

Input #1

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "O. April Fools' Problem (hard)",
    "description": {
      "content": "The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF802O"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "HC#cf_span[2] 的计划相当遥远：例如，我们距离 HC#cf_span[2] 3387 还有 50 多万天，因此我们计划在该版本中准备几十万个问题（我们希望编程竞赛会变得异常流行）。土拨鼠们需要开始工作，它们需要一个良好的计划...\n\n与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。\n\n与中等版本相同。\n\n## Input\n\n与中等版本相同，但限...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given integers $ n $ and $ k $ such that $ 1 \\leq k \\leq n \\leq 500{,}000 $, compute the number of ways to choose $ k $ distinct elements from a set of $ n $ elements, modulo $ 10^9 + 7 $.\n\nThat is, c...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments