H. Pseudo-Random Number Generator

Codeforces

IDCF10250H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is close enough to $50 %$. Your help will be welcome. The input consists of a single line, containing an integer $N$. *Limits* The input satisfies $0 <= N < 2^(63)$. The output should contain a single line with a single integer corresponding to the number of even values in the sequence $S (0), S (1), \\dots, S (N -1)$. ## Input The input consists of a single line, containing an integer $N$.*Limits*The input satisfies $0 <= N < 2^(63)$. ## Output The output should contain a single line with a single integer corresponding to the number of even values in the sequence $S (0), S (1), \\dots, S (N -1)$. [samples]

**Definitions** Let $ n \in \mathbb{Z}_{\geq 0} $ be the number of sheets. Each sheet $ i \in \{1, \dots, n\} $ has two page numbers: $ (i, i+1) $. Let $ \pi \in S_n $ be a permutation of the $ n $ sheets, representing the order from top to bottom of the stack. A *divine pair* is an ordered pair $ (i, j) $ with $ i < j $ (i.e., sheet $ \pi(i) $ is above sheet $ \pi(j) $) such that: $$ \min(\pi(i), \pi(i)+1) > \max(\pi(j), \pi(j)+1) \quad \iff \quad \pi(i) > \pi(j) + 1 $$ Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of divine pairs in permutation $ \pi $. **Constraints** $ 1 \leq t \leq 10^5 $, $ 0 \leq n, k \leq 750 $ **Objective** For each test case $ (n, k) $, compute the number of permutations $ \pi \in S_n $ such that the number of divine pairs is exactly $ k $, modulo $ 987654321 $. That is, compute: $$ f(n, k) = \left| \left\{ \pi \in S_n \,\middle|\, \sum_{1 \leq i < j \leq n} \mathbf{1}_{\pi(i) > \pi(j) + 1} = k \right\} \right| \mod 987654321 $$

API Response (JSON)

{
  "problem": {
    "name": "H. Pseudo-Random Number Generator",
    "description": {
      "content": "As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is cl",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10250H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is cl...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $ be the number of sheets.  \nEach sheet $ i \\in \\{1, \\dots, n\\} $ has two page numbers: $ (i, i+1) $.  \n\nLet $ \\pi \\in S_n $ be a permutation of the $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments