题目
backgrounds
夕阳镇第五幼儿园的zhangzj发现每个幼儿园的好♂友关系都会构成一个图，由于身处图中，zhangzj决定研究这些图，经过1s的思考，他发现这些图有很多种类型，于是他想知道每种类型的图有多少个，但是由于他只有十个手指头、十个脚趾头和一个脑袋，所以他数不过来，只好请你来帮忙。
content
图的定义：图$G$是一个有序二元组$(V,E)$，其中$V$称为点集，$E$称为边集，$E$与$V$不相交。它们亦可写成$(G)$和$E(G)$。
此题中图不允许有重边和自环。
树的定义：树是一种特殊的图，它是一个连通图，且任意删去一条边，它就不连通。
两个图同构的定义：
设这两个图为$G_1=(V_1,E_1)$，$G_2=(V_2,E_2)$：
- 点数相同。
- 如果是一个有标号的图，那么他们同构等价于$E_1=E_2$。
- 如果是一个无标号的图，且存在一种对于$G_1$和$G_2$的标号使得新的两个有标号图同构，那么它们同构。
问题描述：
- 给定一个整数$n$，求$n$个点的有标号的无根树的个数。
- 给定一个整数$n$，求$n$个点的有标号的有根树的个数。
- 给定一个整数$n$，求$n$个点的无标号的无根树的个数。
- 给定一个整数$n$，求$n$个点的无标号的有根树的个数。
- 给定一个整数$n$，求$n$个点的有标号的所有点的度数均为偶数的图的个数。
- 给定一个整数$n$，求$n$个点的有标号的欧拉图的个数。
- 给定一个整数$n$，求$n$个点的有标号的二分图的个数。
求方案数对$m$取模的结果。保证$m$是质数。
input format
一行八个数$m,n_1,n_2,n_3,n_4,n_5,n_6,n_7$，分别为原问题中的$m$和七个问题的$n$。
output format
一行七个数，表示七个问题的答案。
sample input
5 2 2 2 2 2 2 2
sample output
1 2 1 1 1 0 2
constraints
对于$10\%$的数据，$n_1,n_2,n_3,n_4,n_5,n_6,n_7 \leq 5$。
对于$30\%$的数据，$n_1,n_2,n_5 \leq 1000$，$n_3,n_4,n_6,n_7 \leq 10$。
对于$50\%$的数据，$n_1,n_2 \leq 10^7$，$n_5 \leq 10^9$，$n_3,n_4,n_6,n_7 \leq 100$。
对于$100\%$的数据，$1 \leq n_1,n_2,n_5 \leq 10^{18}$，$n_3,n_4,n_6,n_7 \leq 1000$，$1 \leq m \leq 10^9$。
对于每个测试点，如果$7$个答案中有$4$个是对的，那么可以得到$1$分。如果有$6$个是对的，那么可以得到$2$分。如果有$7$个是对的，那么可以得到满分$5$分。
题解
有标号的无根树的个数
学过prufer序列的都知道答案是$n^{n - 2}$。注意不要爆long long，当然$n = 1$需要特判（虽然$1^{-1}=1$但你的快速幂求不出来啊）。
有标号的有根树的个数
无根树随便挑一个根就好了，不难证明这是不重不漏的。答案就是$n^{n - 1}$。
无标号的无根树的个数
在做之前，先假设我们会求无标号的有根树个数，至于怎么求等会再说。（嗯我就是故意按照题目顺序的）
先设由$n$个结点组成的无标号的有根树有$a_n$个。
直接做似乎不太好做，我们不妨换个角度，考虑容斥。我们只需要求出因重复而需要减去的有根树的个数即可。
在所有的有根树中，选取连接根结点和它的第一个儿子的一条边，它两端可以看做是两棵有根树连接上来的。那么，两端的树交换过来的话，仍然是一棵同构的无根树，因此枚举一端的树的大小，就得到如下的式子：
$$ans_n = a_n - \sum_{i = 1}^{\lfloor \frac{n}{2}\rfloor}a_ia_{n - i}$$
看起来做完了，但是如果$n$是偶数，可能会出现两棵树完全一样的情况，这相当于我们多减了，需要加回来。如果两棵树大小都是$\dfrac{n}{2}$，那么它们不同的情况只有$\dfrac{a_{\frac{n}{2}}(a_{\frac{n}{2}} - 1)}{2}$种，但我们减了$a_{\frac{n}{2}}^2$种，因此还要加回来$\dfrac{a_{\frac{n}{2}}(a_{\frac{n}{2}} + 1)}{2}$种。
说的有点乱，本质上就是枚举边两端的有根树大小，减去重复的，加上多减的，就完了。
无标号的有根树的个数
警告：公式恐惧症患者请连按几次PageDown键直接阅读结论。
既然是有根树，我们不妨枚举根的所有儿子，这样就可以通过小规模的问题来解决更大规模的问题。
为了方便，记$i$个结点构成的无编号的有根树有$a_i$个。
考虑大小为一定值的儿子的个数，不妨记以这些儿子为根的子树中，大小为$i$的有$c_i(\ge 0)$个，那么显然有
$$\sum_{i = 1}^{n - 1}ic_i = n - 1$$
对于每一种大小，显然它共有$a_i$种构造方法。在这$c_i$棵子树中，设采用第$j$种构造方法的有$x_{i,j}(\\ge 0)$种，那么
$$\sum_{j = 1}^{a_i}x_{i, j} = c_i$$
现在我们要求这个方程有多少组解。令$y_{i, j} = x_{i, j} + 1$，显然$y_i$的解与$x_i$的解是一一对应的，同时对于$y_i$有
$$\sum_{j = 1}^{a_i}y_{i, j} = c_i + a_i, y_{i, j} > 0$$
利用组合数学中的隔板法，不难得出解数为$C_{a_i + c_i - 1}^{a_i - 1}$，也就是$C_{a_i + c_i - 1}^{c_i}$。当然，不同的子树大小对应的方案数互补影响，可以利用乘法原理计算。因此，总结上面所说的内容，对于每一种划分方案${c}$，方案总数为
$$\prod_{i = 1}^{n - 1}C_{a_i + c_i - 1}^{c_i}$$
最后把所有的划分方案加起来，就是
$$a_n = \sum_{\sum_{i = 1}^{n - 1}(ic_i) = n - 1}\left (\prod_{i = 1}^{n - 1}C_{a_i + c_i - 1}^{c_i}\right)$$
这就可以递推了嘛！你要问复杂度？这取决于$\sum_{i = 1}^{n - 1}ic_i = n - 1$的解数，$n$比较小时并不是很大哦~
好了不开玩笑了，这东西怎么能跑过$n = 1000$呢。要优化这算法，我们还需要更先进的姿势。为了方便，设$a_0 = 0$。
考虑数列$\{a_n\}$的母函数
$$A(x) = \sum_{i = 0}^{+\infty}a_ix^i$$
我们想把它搞成一个好看的形式，也就是说我们要造一个有限项的函数，让它等价于这个东西。
先介绍一点基础知识，下面的组合学方法可以沟通有限和无限。组合数自古以来都是定义在非负整数集上的，因为负数的阶乘没有定义。但如果我们换一种计算方法，也就是这么算：
$$C_{n}^{m} = \frac{n!}{m!(n - m)!} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j}$$
就是从$n$开始往下算“阶乘”，从$1$开始往上算“阶乘”，各算$m$次，相除便是答案。这样计算的话，对于$n$为负数的情况也可以兼容了，因此定义
$$C_{n}^{m} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j}, n \in {\mathbb Z}, m \geq 0$$
我们不妨试试，如果$n$为负数会算出来什么。经过一番整理，其实就是
$$C_{n}^{m} = \frac{\prod_{i = n - m + 1}^{n}i}{\prod_{j = 1}^{m}j} = \frac{\prod_{i = -n}^{-n + m - 1}(-i)}{\prod_{j = 1}^{m}j} = (-1)^m\frac{\prod_{i = -n}^{-n + m - 1}i}{\prod_{j = 1}^{m}j} = (-1)^mC_{-n + m - 1}^{m}, n < 0, m \geq 0$$
这样我们就会算推广的组合数了。不难发现，因为定义的等价性，二项式定理似乎也可以推广，也就是
$$(1 + x)^{n} = \sum_{k = 0}^{+\infty}C_{n}^{k}x^k = \sum_{k = 0}^{+\infty}(-1)^kC_{-n + k - 1}^{k}x^k, n < 0$$
好吧以上东西都是为了方便理解瞎BB的，但是这个式子是正确的。这一步非常关键，因为它把一个分式和一个无穷级数画上了等号。如果把$n = -1$带入，那么就是
$$(1 + x)^{-1} = \sum_{k = 0}^{+\infty}(-1)^kC_{k}^{k}x^k = \sum_{k = 0}^{+\infty}(-x)^k$$
这是显然正确的，运用等比数列求和即可证明。
然后问题就是找到一个分式满足展开后的形式满足$\{a_n\}$的递推式。这是很困难的，还好有前人已经找出来了。
首先我们有如下式子：
$$(1 - x^r)^a = \sum_{k = 0}^{+\infty}C_{-a + k - 1}^{k}x^{rk}, a < 0$$
考虑计算
$$\prod_{i = 1}^{+\infty}(1 - x^i)^{-a_i}$$
的展开式中$x^n$项的系数，我们可以枚举这$n$个$x$分别来自于哪一项，这里就和上面分析子树的那一段一模一样了。最后的结果我们也很熟悉，就是
$$\sum_{\sum_{i = 1}^{n}(ic_i) = n}\left (\prod_{i = 1}^{n}C_{a_i + c_i - 1}^{c_i}\right)$$
它恰好等于$a_{n + 1}$，为了满足生成函数的性质，我们把它乘上一个$x$，就得到生成函数$A$了：
$$A(x) = \frac{x}{\prod_{i = 1}^{+\infty}(1 - x^i)^{a_i}}$$
然而这并没有卵用，毕竟右面还是有无限项，不要慌嘛。我们把两边都取个对数看看：
$$\ln A(x) = \ln x - \sum_{i = 1}^{+\infty}a_i\ln(1 - x^i)
= \ln x + \sum_{i = 1}^{+\infty}a_i\ln(\frac{1}{1 - x^i})$$
注意到右面有出现了分式，还是在对数里面，我们考虑积分相关的知识。为了方便，这里直接把$x^i$作为积分变量，设$t = x^i$，那么由于$(\ln\dfrac{1}{1 - t})‘ = \dfrac{1}{1 - t}$，所以$\int\dfrac{1}{1 - t}dt = \ln\dfrac{1}{1 - t}$，所以
$$\ln\frac{1}{1 - t} = \int\frac{1}{1 - t}dt = \int\sum_{k = 0}^{+\infty}t^k = \sum_{k = 1}^{+\infty}\frac{1}{k}t^{k}$$
带回上式就是
$$\ln A(x) = \ln x + \sum_{i = 1}^{+\infty}\left(a_i\sum_{k = 1}^{+\infty}\frac{1}{k}x^{ik}\right)$$
交换一下求和符号，就是
$$\ln A(x) = \ln x + \sum_{k = 1}^{+\infty}\left(\frac{\sum_{i = 1}^{+\infty}a_ix^{ik}}{k}\right)$$
根据生成函数的定义，可以化为
$$\ln A(x) = \ln x + \sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)$$
这已经很漂亮了，我们考虑两边再取一下指数。为了方便，定义$\exp(x) = e^x$：
$$A(x) = x\exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)$$
然后对两边求导得到
$$A’(x) = \exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right) + x\exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)‘$$
又因为
$$\frac{A(x)}{x} = \exp\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)$$
所以
$$A’(x) = \frac{A(x)}{x} + A(x)\left(\sum_{k = 1}^{+\infty}\left(\frac{A(x^k)}{k}\right)\right)‘$$
把右面的那一坨东西用一下求导公式，就成了
$$\frac{dA(x)}{d(x)} = \frac{A(x)}{x} + A(x)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\frac{dA(x^k)}{d(x^k)}\right)\right)$$
$$\frac{dA(x)}{d(x)} - \frac{A(x)}{x} = A(x)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\frac{dA(x^k)}{d(x^k)}\right)\right)$$
根据多项式求导的计算方法，我们可以展开成这样：
$$\sum_{i = 0}^{+\infty}(i + 1)a_{i + 1}x^i - \sum_{i = 0}^{+\infty}a_{i + 1}x^i = \left(\sum_{i = 0}^{+\infty}a_{i}x^i\right)\left(\sum_{k = 1}^{+\infty}\left( x^{k - 1}\sum_{j = 1}^{+\infty}ja_jx^{k(j - 1)}\right)\right)$$
稍微变形一下就是
$$\sum_{i = 0}^{+\infty}ia_{i + 1}x^i = \left(\sum_{i = 0}^{+\infty}a_{i}x^i\right)\left(\sum_{j = 1}^{+\infty}\left( ja_j\sum_{k = 1}^{+\infty}x^{jk - 1}\right)\right)$$
现在我们只考虑$a_{n + 1}$。显然还需要枚举一下不同的$j$，假设确定了$j$，那么对于每一个合法的$k$，对应的$i$也是唯一确定的，所以我们有
$$na_{n + 1} = \sum_{j = 1}^{n}ja_j\sum_{k = 1}^{\lfloor \frac{n}{j} \rfloor}a_{n + 1 - jk}$$
也就是
$$a_{n + 1} = \frac{1}{n}\sum_{j = 1}^{n}ja_j\sum_{k = 1}^{\lfloor \frac{n}{j} \rfloor}a_{n + 1 - jk}$$
这样的递推关系就很显然了嘛！只需要枚举$j, k$就好了。