#P4645. graph

    ID: 3785 传统题 2000ms 512MiB 尝试: 13 已通过: 4 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学Prüfer 序列数论快速幂多项式与生成函数普通生成函数导数积分转化动态规划计数 DP双射计数模拟与实现技巧高精度乘法高精度除法Pascal 递推费马小定理构造与建模奇偶性分析图论无向连通分量CF2800

graph

graph

题目描述

以下所有图均为无向简单图。对于有标号的图,顶点分别标为 11 至 nn。对于无标号的图,只按同构类型计数。有根树在计数时还要区分树根,同构须保持根的位置。

分别计算下列七个数量。

  1. n1n_1 个顶点的有标号无根树数量。
  2. n2n_2 个顶点的有标号有根树数量。
  3. n3n_3 个顶点的无标号无根树数量。
  4. n4n_4 个顶点的无标号有根树数量。
  5. n5n_5 个顶点的有标号图数量,要求所有顶点的度数均为偶数。
  6. n6n_6 个顶点的有标号欧拉图数量,要求图连通且所有顶点的度数为偶数。
  7. n7n_7 个顶点的有标号二分图数量。二分只要求存在,划分方法不计入答案。

每项结果都对质数 mm 取模。

输入格式

一行八个整数 m,n1,n2,n3,n4,n5,n6,n7m,n_1,n_2,n_3,n_4,n_5,n_6,n_7。

输出格式

输出一行七个整数,依次表示上述七项的答案。

5 2 2 2 2 2 2 2
1 2 1 1 1 0 2

数据范围

1<m<1091<m<10^9,且 mm 为质数。

1≤n1,n2,n5≤10181\le n_1,n_2,n_5\le10^{18},1≤n3,n4,n6,n7≤10001\le n_3,n_4,n_6,n_7\le1000。