#P18617. Directed Vertex Cacti
Directed Vertex Cacti
Directed Vertex Cacti
给定两个整数 。
求满足以下全部条件的有向图 的数量:
- 恰有 个顶点,标号为 ;
- 没有自环,也没有同向重边;
- 每个顶点至多属于一个简单有向环;
- 恰有 条边不属于任何有向环。
如果存在标号为 的顶点,使得有向边 只在两个图中的一个里存在,则这两个图不同。
简单有向环指沿边方向行走、除首尾重合外不重复经过顶点的环。
输入格式
仅一行,两个整数 ()。
输出格式
输出满足条件的图的数量对 取模的结果。
样例输入 1
3 1
样例输出 1
18
样例输入 2
4 4
样例输出 2
360
样例输入 3
39847 348708
样例输出 3
983575456
说明
“没有重边”是指不能存在两条不同的 边。但可以同时存在 和 ,这两条边构成长度为 的简单有向环。
只统计不属于任何环的边,图的总边数可以大于 。不要求图连通。