「ALFR Round 1」D 小山的元力

Luogu

IDLGP10380

Time2000ms

Memory512MB

DifficultyP4

O2优化

小山有 $n$ 个相同的元素，他想将这 $n$ 个元素分为 $m$ 堆，显然有很多种分法。对于每种分法，定义 $a_i$ 为第 $i$ 堆的元素数量，$b_i=i!\times a_i$（其中 $i!$ 表示 $i$ 的阶乘），以及 $c=\sum\limits_{i=1}^mb_i$。而小山的元力为所有分法的 $c$ 值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对 $p$ 取模（保证 $p$ 为质数）。 ## Input 一行三个整数 $n,m,p$，含义见**题目描述**。 ## Output 一个数表示小山的元力。 [samples] ## Note ### 样例解释将 $3$ 个元素分为 $2$ 堆的方案为： 1. `0 3` 2. `1 2` 3. `2 1` 4. `3 0` 小山的元力为：$(1!\times0+2!\times3)+(1!\times1+2!\times2)+(1!\times2+2!\times1)+(1!\times3+2!\times0)=18$。 ### 数据范围 | 子任务 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $0$ | $20$ | $n,m\le5$ | | $1$ | $80$ | - | 对于 $100\%$ 的数据，$1\le n,m\le10^6$，$1\le p\le10^7$。

Samples

Input #1

3 2 37

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「ALFR Round 1」D 小山的元力",
    "description": {
      "content": "小山有 $n$ 个相同的元素，他想将这 $n$ 个元素分为 $m$ 堆，显然有很多种分法。对于每种分法，定义 $a_i$ 为第 $i$ 堆的元素数量，$b_i=i!\\times a_i$（其中 $i!$ 表示 $i$ 的阶乘），以及 $c=\\sum\\limits_{i=1}^mb_i$。而小山的元力为所有分法的 $c$ 值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对 $p$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10380"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小山有 $n$ 个相同的元素，他想将这 $n$ 个元素分为 $m$ 堆，显然有很多种分法。对于每种分法，定义 $a_i$ 为第 $i$ 堆的元素数量，$b_i=i!\\times a_i$（其中 $i!$ 表示 $i$ 的阶乘），以及 $c=\\sum\\limits_{i=1}^mb_i$。而小山的元力为所有分法的 $c$ 值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对 $p$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments