[GDKOI2023 提高组] 错排

Luogu

IDLGP10103

Time3000ms

Memory1024MB

DifficultyP7

2023广东

小 X 最近学习了错排问题，于是开始思考一个关于它的变种问题：有多少个长度为 $n$ 的排列 $p$，满足对于 $i \le m$ 的位置满足 $p_i > m$，且对于所有位置 $i$ 都满足 $p_i \ne i$？小 X 一共想出了 $T$ 个这样的问题，你能告诉他每个问题的答案吗？由于答案可能过大，你只需要求出答案对 $998244353$ 取模后的值即可。 ## Input 第一行输入一个整数 $T$，表示询问组数。接下来的 $T$ 行，每行输入两个整数 $ n, m$。 ## Output 输出 $T$ 行，每行一个整数表示答案对 $998244353$ 取模后的值。 [samples] ## Note 对于 100% 的数据，$0 ≤ T ≤ 2 \times 10^5$，$0 ≤ m ≤ n ≤ 2 \times 10^5$。本题采用子任务捆绑测试。 - Subtask 1 (1pts)：保证 $T = 0$。 - Subtask 2 (9pts)：保证 $T ≤ 10$，$n, m ≤ 8$。 - Subtask 3 (10pts)：保证 $m = 0$。 - Subtask 4 (20pts)：保证 $n, m ≤ 5000$。 - Subtask 5 (20pts)：保证 $T ≤ 10$。 - Subtask 6 (40pts)：无特殊性质。

Samples

Input #1

6
8 0
8 4
100 10
1000 100
10000 1000
100000 10000

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2023 提高组] 错排",
    "description": {
      "content": "小 X 最近学习了错排问题，于是开始思考一个关于它的变种问题：有多少个长度为 $n$ 的排列 $p$，满足对 于 $i \\le m$ 的位置满足 $p_i > m$，且对于所有位置 $i$ 都满足 $p_i \\ne i$？ 小 X 一共想出了 $T$ 个这样的问题，你能告诉他每个问题的答案吗？ 由于答案可能过大，你只需要求出答案对 $998244353$ 取模后的值即可。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10103"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 最近学习了错排问题，于是开始思考一个关于它的变种问题：有多少个长度为 $n$ 的排列 $p$，满足对\n于 $i \\le m$ 的位置满足 $p_i > m$，且对于所有位置 $i$ 都满足 $p_i \\ne i$？\n\n小 X 一共想出了 $T$ 个这样的问题，你能告诉他每个问题的答案吗？\n\n由于答案可能过大，你只需要求出答案对 $998244353$ 取模后的值即可。\n\n## Input\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments