[ZJOI2022] 树

Luogu

IDLGP8329

Time2000ms

Memory1024MB

DifficultyP7

各省省选2022浙江O2优化容斥原理

九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。第一棵树的生成方式是： 1. 节点 $1$ 作为树的根。 2. 对于 $i \in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。第二棵树的生成方式是： 1. 节点 $n$ 作为树的根。 2. 对于 $i \in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。九条可怜希望对于任意 $i \in [1, n]$，若第一棵树中的节点 $i$ 为叶子，那么第二棵树中的节点 $i$ 为非叶子；若第一棵树中的节点 $i$ 为非叶子，那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。九条可怜希望你统计生成两棵树的方案数是多少。具体地，你需要对于所有 $n \in [2, N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$，两种方案中它的父亲不同。因为答案可能很大，你只需要输出答案对 $M$ 取模后的结果。 ## Input 第一行输入两个整数 $N, M$，表示树的节点上限以及模数。 ## Output 输出 $N - 1$ 行，每行一个整数。具体地，第 $i$ 行输出 $n = i + 1$ 时的答案对 $M$ 取模后的值。 [samples] ## Background 一年一度的 ZJOI 又要举办了，但是老牌出题人九条可怜突然有急事要回趟英国。 “就交给你们啦！一定没有问题 desu！”，说完可怜就跑远了。忍，爱丽丝，绫和阳子目送着远去的可怜，感到有点茫然，毕竞，ZJOI 只剩不到三星期了。既然是可怜酱留下的任务，那我们一定要努力完成了，毕竟我才是姐姐”，爱丽丝说。于是众人就开始热火朝天地出题了，“希望这是第一次也是最后一次了” 大家都不约而同地想。同时，题目主角就定为九条可怜了！ ## Note 对于所有测试点：保证 $2 \le N \le 500$，$10 \le M \le 2^{30}$。每个测试点的具体限制见下表： | 测试点编号 | $N \le$ | 特殊限制 | |:-:|:-:|:-:| | $1$ | $10$ | 无 | | $2$ | $20$ | 保证 $M$ 为质数 | | $3$ | $50$ | 无 | | $4$ | $50$ | 保证 $M$ 为质数 | | $5$ | $100$ | 无 | | $6$ | $100$ | 保证 $M$ 为质数 | | $7$ | $500$ | 无 | | $8$ | $500$ | 保证 $M$ 为质数 | | $9$ | $500$ | 无 | | $10$ | $500$ | 保证 $M$ 为质数 |

Samples

Input #1

5 998244353

Output #1

Input #2

见附件中的 tree/tree_ex2.in

Output #2

见附件中的 tree/tree_ex2.ans

API Response (JSON)

{
  "problem": {
    "name": "[ZJOI2022] 树",
    "description": {
      "content": "九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。 第一棵树的生成方式是： 1. 节点 $1$ 作为树的根。 2. 对于 $i \\in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。 第二棵树的生成方式是： 1. 节点 $n$ 作为树的根。 2. 对于 $i \\in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8329"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "九条可怜是一个喜欢树的女孩子，她想生成两棵均有 $n$ 个节点的树。\n\n第一棵树的生成方式是：\n\n1. 节点 $1$ 作为树的根。\n2. 对于 $i \\in [2, n]$，从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。\n\n第二棵树的生成方式是：\n\n1. 节点 $n$ 作为树的根。\n2. 对于 $i \\in [1, n - 1]$，从 $[i + 1, n]$ 中选取一个节点作...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments