本文主要是介绍DTOJ 4749. 计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
计数弱智题目 7 i n 1 7 in 1 7in1，就算你不是都会算也可以，本题根据你答对多少个问题来决定你得到多少分
第一类问题：求 n n n 个点构成的有标号无根树有多少种
第二类问题：求 n n n 个点构成的有标号有根树有多少种
第三类问题：求 n n n 个点构成的无标号无根树有多少种
第四类问题：求 n n n 个点构成的无标号有根树有多少种
第五类问题：求 n n n 个点构成的有标号所有点的度数为偶数的图有多少种
第六类问题：求 n n n 个点构成的有标号欧拉图有多少种
第七类问题：求 n n n 个点构成的有标号二分图有多少种
对质数 p p p 取模
对于 10 % 10\% 10% 的数据， x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≤ 5 x_1,x_2,x_3,x_4,x_5,x_6,x_7 \le 5 x1,x2,x3,x4,x5,x6,x7≤5
对于 30 % 30\% 30% 的数据, x 1 , x 2 , x 5 ≤ 1000 , x 3 , x 4 , x 6 , x 7 ≤ 10 x_1,x_2,x_5 \le 1000,x_3,x_4,x_6,x_7 \le 10 x1,x2,x5≤1000,x3,x4,x6,x7≤10
对于 50 % 50\% 50% 的数据， x 1 , x 2 , x 5 ≤ 1 0 9 ， x 3 , x 4 , x 6 , x 7 ≤ 100 x_1,x_2,x_5 \le 10^9，x_3,x_4,x_6,x_7 \le 100 x1,x2,x5≤109，x3,x4,x6,x7≤100
对于 100 % 100\% 100% 的数据， x 1 , x 2 , x 5 ≤ 1 0 18 , x 3 , x 4 , x 6 , x 7 ≤ 1000 , p ≤ 1 0 9 + 7 x_1,x_2,x_5 \le 10^{18},x_3,x_4,x_6,x_7 \le 1000, p \le 10^9+7 x1,x2,x5≤1018,x3,x4,x6,x7≤1000,p≤109+7
数据保证了 p > x 3 , x 4 , x 6 , x 7 p>x_3,x_4,x_6,x_7 p>x3,x4,x6,x7，应该不会出什么怪事
对于每个测试点，答对7个得5分，答对5个得3分，答对3个得1分
如果你的输出不是7个数， spj会给你0分
题解
前两个点直接prufer序即可（所以没分）。
对于3,4考虑DP：由于无标号为避免重复，一个点转移时应按照子树的某种顺序转移。设 f [ i ] [ j ] f[i][j] f[i][j]为i个点组成若干子树，子树大小不降，最后一个子树大小为 j j j的方案数，枚举最后一个子树选了几个，用插板法计算可重无标号组合即可。注意这里可以不需要记第二维，直接一开始枚举 j j j转移即可保证从小到大。
对于5，这种数据范围很大却连DP都没什么思路的问题当然考虑一些巧妙性质了。发现无论前 n − 1 n-1 n−1个点是怎么样的，第n个点一定有唯一确定方案使它合法，于是答案为 2 ( n − 1 ) ∗ ( n − 2 ) / 2 2^{(n-1)*(n-2)/2} 2(n−1)∗(n−2)/2。
那么6就是满足5并且联通的图的个数了，也是很套路的东西，设一个总的方案和联通的方案，考虑 1 1 1号点所在连通块大小，相互转移一下即可。
对于7也是类似的思路，注意到联通的二分图只会有两种同构的情况，转移的时候 ∗ 2 *2 ∗2即可。
这篇关于DTOJ 4749. 计数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
