[集训队互测 2023] 基础寄术练习题

Luogu

IDLGP10005

Time2000ms

Memory512MB

DifficultyP7

集训队互测2023O2优化

对于长度为 $n$ 的序列 $a$，定义 $f(a)=\dfrac{1}{\prod\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\{a_n\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\le k\le 2$**。考虑所有满足以下三个条件的序列 $a$： - $a$ 的长度为 $n$。 - $\forall i,j$，$a_i\ne a_j$。 - $1\le a_i\le m$。求它们的 $f(a)$ 之和，答案对 $p$ 取模。保证 $p$ 是一个质数。 ## Input 第一行四个整数 $n,m,k,p$，分别代表序列长度，序列元素的上界和模数。 ## Output 一行一个整数表示答案对 $p$ 取模后的结果。 [samples] ## Note 对于所有数据，保证 $2\le n\le m\le 100$，$10^8<p<1.07\times 10^9$ 且 $p$ 为质数，$1\le k\le 2$。 - Subtask 1 (10 pts)：$m\le 20$。 - Subtask 2 (25 pts)：$k=1$。 - Subtask 3 (15 pts)：$n=m\le 30$。 - Subtask 4 (10 pts)：$m\le 30$。 - Subtask 5 (15 pts)：$m\le 40$。 - Subtask 6 (10 pts)：$m\le 70$。 - Subtask 7 (15 pts)：$m\le 100$。

Samples

Input #1

2 3 2 1000000007

Output #1

966666675

Input #2

3 5 2 998244353

Output #2

148276980

Input #3

6 10 2 1004535809

Output #3

622165218

Input #4

15 20 2 1064822107

Output #4

53789887

Input #5

30 40 1 265371653

Output #5

179937201

API Response (JSON)

{
  "problem": {
    "name": "[集训队互测 2023] 基础寄术练习题",
    "description": {
      "content": "对于长度为 $n$ 的序列 $a$，定义 $f(a)=\\dfrac{1}{\\prod\\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\\{a_n\\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\\le k\\le 2$**。 考虑所有满足以下三个条件的序列 $a$： - $a$ 的长度为 $n$。 - $\\forall i,j$，$a_i\\ne a_j$。 - $1\\le a",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10005"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于长度为 $n$ 的序列 $a$，定义 $f(a)=\\dfrac{1}{\\prod\\limits_{i=k}^ns_i}$，其中 $s_i$ 为 $\\{a_n\\}$ 的前缀和数组，**$k$ 是给定的常数且 $1\\le k\\le 2$**。\n\n考虑所有满足以下三个条件的序列 $a$：\n\n- $a$ 的长度为 $n$。\n- $\\forall i,j$，$a_i\\ne a_j$。\n- $1\\le a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments