Circular Distance

AtCoder

IDagc068_a

Time2000ms

Memory256MB

Difficulty—

There is a circle with circumference $L$, and $L$ people are standing equally spaced along the circumference. They are labeled as person $0, 1, \cdots, L-1$ in clockwise order. Consider choosing $N$ from these $L$ people. The **cost** of a choice is defined as follows. * For every pair of persons among the $N$ chosen people, find the minimum distance one person has to move along the circumference to reach the other person's position. The maximum value among these distances is the cost. Find the sum of costs over all possible choices, modulo $998244353$. ## Constraints * $2 \leq N \leq L \leq 10^6$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $L$ $N$ [samples]

Samples

Input #1

4 2

Output #1

8

The choices of $N$ people and their corresponding costs are as follows:

*   $(0,1)$: cost $1$
*   $(0,2)$: cost $2$
*   $(0,3)$: cost $1$
*   $(1,2)$: cost $1$
*   $(1,3)$: cost $2$
*   $(2,3)$: cost $1$

The sum of these costs, $8$, is the answer.

Input #2

5 5

Output #2

2

We can only choose all of them. In this case, the cost is $2$.

Input #3

13 5

Output #3

Input #4

1000000 100000

Output #4

664396470

API Response (JSON)

{
  "problem": {
    "name": "Circular Distance",
    "description": {
      "content": "There is a circle with circumference $L$, and $L$ people are standing equally spaced along the circumference. They are labeled as person $0, 1, \\cdots, L-1$ in clockwise order. Consider choosing $N$ f",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc068_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a circle with circumference $L$, and $L$ people are standing equally spaced along the circumference. They are labeled as person $0, 1, \\cdots, L-1$ in clockwise order. Consider choosing $N$ f...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments