P5333 [JSOI2019] 神经网络 【树形dp,EGF】

标签：typedef   etc   turn   mod   printf   ++   注意   div   main   

题目链接

题目描述：给你 \(m\) 棵树，第 \(i\) 棵有 \(k_i\) 个节点。将这 \(m\) 棵树放在一起，任意两棵树之间连成完全二分图，得到了一个 \(\sum k_i\) 个点的无向简单联通图，求哈密顿回路个数。

数据范围：\(m\le 300,\sum k_i\le 5000\)

首先强制从第 \(1\) 棵树的 \(1\) 号节点开始连接，可以看成每次走其中一棵树上面的一条链，然后跨越到另一颗树上去，然后计数这个链的排列。所以答案与每棵树的形态没什么关系，求出 \(f_i\) 表示当前树划分为 \(i\) 条链的方案数，这个可以 \(O(k^2)\) dp 做，设 \(dp_{x,i,0/1/2}\) 表示以 \(x\) 为根的子树中，划分为了 \(i\) 条链，\(x\) 单独成链/为链端点/为链中间点 的方案数，转移显然...显然么？好吧因为这里的链是有方向的，所以注意有些地方有 \(2\) 的系数。

然后就要计数这些链的排列，是不是只能用 EGF 了啊... 你可以把每棵树对答案的贡献设为一个 EGF，然后计算答案的时候就把所有 EGF 乘起来就可以了。

对于除了第一棵之外的树，要求同一棵树的两条链不能相邻，所以可以用容斥。

对于第一棵树，第一条链不应参与排列，而且最后一条链不能在第一棵树里。

#include
#define Rint register int
using namespace std;
typedef long long LL;
template
inline void read(T &x){
    int ch = getchar(); x = 0;
    bool f = false;
    for(;ch  ‘9‘;ch = getchar()) f |= ch == ‘-‘;
    for(;ch >= ‘0‘ && ch > 31) & mod;}
inline void add(int a, int b){
    to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;
}
inline int ksm(int a, int b){
    int res = 1;
    for(;b;b >>= 1, a = (LL) a * a % mod) if(b & 1) res = (LL) res * a % mod;
    return res;
}
inline void init(int m){
    fac[0] = 1;
    for(Rint i = 1;i 

P5333 [JSOI2019] 神经网络 【树形dp,EGF】

标签：typedef   etc   turn   mod   printf   ++   注意   div   main   

原文地址：https://www.cnblogs.com/AThousandMoons/p/13052604.html