[JRKSJ R4] Stirling

Luogu

IDLGP8143

Time1000ms

Memory128MB

DifficultyP3

数学2022洛谷原创

对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\forall 1\le i\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。给定 $n$，求有多少个 $[1,n]$ 的排列满足其生成图恰有偶数个环（自环同样计入）。 ## Input 一个整数 $n$。 ## Output 一个整数，表示答案。答案对 $998244353$ 取模。 [samples] ## Background 可能对您无用的提示： $$f(n)=\sum_{i=0}^n \begin{Bmatrix} n\\i\end{Bmatrix}g(i) \leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} \begin{bmatrix} n\\i\end{bmatrix} f(i)$$ ## Note ### 样例 $1$ 解释这些排列满足条件： $$\{1,3,2\}$$ $$\{2,1,3\}$$ $$\{3,2,1\}$$ ### 数据规模对于 $20\%$ 的数据，$n\le 10$。\ 对于 $50\%$ 的数据，$n\le 500$。\ 对于 $100\%$ 的数据，$1\le n\le 10^6$。

Samples

Input #1

Output #1

Input #2

Output #2

430461019

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R4] Stirling",
    "description": {
      "content": "对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\\forall 1\\le i\\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。 给定 $n$，求有多少个 $[1,n]$ 的排列满足其生成图恰有偶数个环（自环同样计入）。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8143"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于 $[1,n]$ 的排列 $p$，定义其“生成图”为：该图有 $n$ 个点，且 $\\forall 1\\le i\\le n$，无向边 $(i,p_i)$ 存在且仅存在这些边。\n\n给定 $n$，求有多少个 $[1,n]$ 的排列满足其生成图恰有偶数个环（自环同样计入）。\n\n## Input\n\n一个整数 $n$。\n\n## Output\n\n一个整数，表示答案。答案对 $998244353$ 取模。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments