[THUPC 2023 决赛] 阴阳阵法

Luogu
IDLGP9385
Time2000ms
Memory1024MB
DifficultyP7
动态规划 DP2023O2优化THUPC
有一张图,图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同,黑点之间两两不同。 每个节点有一条出边,每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。 此时共有 $(n+m)^{n+m}$ 个方案,每个方案是一个有向基环树森林。 称一个方案是好的当且仅当其满足以下条件: - 任何一个黑点都指向一个白点, - 每个环上的黑点数量和白点数量的乘积是偶数。 你需要求出所有方案中好的方案数量,对输入模数 $P$ 取模。 ## Input 输入一行三个整数 $n,m,P$,意义如题目描述所述。 ## Output 输出一行一个整数表示答案。 [samples] ## Background “余于久远之书,见一阴阳阵,必可助君征服九州。用此阵,须出诸阴阳大将。所谓阴将者,武勇而玉恶;所谓阳将者,善谋时且忠厚。凡阴阳阵,各将皆须择一将,以通之。又有两法皆牢记,不可即弱阵:一曰阴援阴,易激性情,或避之;二曰援与环,环阴与阳同,守以衡……” 正当你准备征服九州时,你仿佛听见一个熟悉的声音在远处喊:“工作的时候不准睡觉,你这样会被开除的……”你终于回过神来,发现你的 XCPC 队友在旁边熟练地拧着螺丝,流水线前已经漏过几个不合格的工品。刚刚什么都没发生啊,你哀叹道,但是…… ## Note ### 样例 1 解释 考虑黑点必须连向白点的限制共有 $3 \times 3 \times 2 = 18$ 种方案,其中一个黑点和一个白点构成一个环的方案非法。选择一个白点和黑点构成环的方案数为 $2$,剩下的一个白点有三种方案,因此非法的方案数为 $2 \times 3 = 6$,答案为 $18-6=12$。 ### 数据规模与约定 对于所有测试数据,$1 \le n,m \le 2000$,$1 \le P \le 10^9$。 ### 提示 你可能需要注意常数对算法效率产生的影响。 ### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)决赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。
Samples
Input #1
2 1 1000000
Output #1
12
Input #2
8 8 8888888
Output #2
2973992
Input #3
1000 1000 123456789
Output #3
55105667
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2023 决赛] 阴阳阵法",
    "description": {
      "content": "有一张图,图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同,黑点之间两两不同。 每个节点有一条出边,每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。 此时共有 $(n+m)^{n+m}$ 个方案,每个方案是一个有向基环树森林。 称一个方案是好的当且仅当其满足以下条件: - 任何一个黑点都指向一个白点, - 每个环上的黑点数量和白点数量的乘积是偶数。 你需要求出所有方",
      "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": "LGP9385"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一张图,图上有 $n$ 个白点和 $m$ 个黑点。白点之间两两不同,黑点之间两两不同。\n\n每个节点有一条出边,每个节点出边指向的节点可以在 $n+m$ 个节点中任意选择。\n\n此时共有 $(n+m)^{n+m}$ 个方案,每个方案是一个有向基环树森林。\n\n称一个方案是好的当且仅当其满足以下条件:\n\n- 任何一个黑点都指向一个白点,\n- 每个环上的黑点数量和白点数量的乘积是偶数。\n\n你需要求出所有方...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments