HDU6954 Minimum spanning tree
打个表，发现所有质数和(2)连边，合数一定是和其约数连边；于是搞个筛，分别求质数和合数的前缀和即可。
HDU6955 Xor sum
搞个前缀和，转化为在一个序列里找到最近的两个点满足异或和等于(k)。搞个Trie，在树上维护最近位置，贪心即可。代码
2021牛客暑期多校训练营4D Rebuild Tree
题意大概是在树上断(k)条边再连(k)条边，求能构成多少种不同的树。
断(k)条边会生成 (k+1)个连通块，连边相当于把这(k+1)个连通块当成点。考虑prufer序列，设第(i)个连通块在prufer中出现次数为(c_i)，则生成树种类为：
[sum_{sum c=k-1}frac{(k-1)!}{prod _{i=1}^{k+1}c_i!}prod_{i=1}^{k+1}s_i^{c_i+1}
]
其中(s_i)为第(i)个连通块的大小,(prod_{i=1}^{k+1}s_i^{c_i+1})是考虑了连通块内不同点的连边，这样乘法结合律一下可以使得一条边((i,j))的贡献是(s_j imes s_j)。
化一下式子大概是长这样
[(k-1)!prod_{i=1}^{k+1}s_isum_{sum c=k-1}prod_{i=1}^{k+1}frac{s_i^{c_i}}{c_i!}
]
搞一个指数生成函数的话就会发现(sum_{sum c=k-1}prod_{i=1}^{k+1}frac{s_i^{c_i}}{c_i!}=[x^{k-1}]prod_{i=1}^{k+1}e^{s_ix}=[x^{k-1}]e^{nx}=frac{n^{k-1}}{(k-1)!})，这样的话答案就只是(n^{k-1}prod_{i=1}^{k+1}s_i)，可以在树上搞一个背包状物。
直接在dp状态中记录连通块大小会直接去世，一个经典的转化是把(prod_{i=1}^{k+1}s_i)理解为从每个连通块里选一个点的方案数。于是用(f_{i,j,0/1})表示在(i)的子树里断了(j)条边，顶部连通块是否选点的方案数，可以做到(O(nk))。代码。
2021牛客暑期多校训练营4B Sample Game
设(f_{i,0/1/2})表示以(i)结尾的所有不降序列的概率( imes)长度的0/1/2次方。
答案就是
[sum_{i=1}^np_isum_{j=i+1}^nf_{j,2}+2 imes f_{j,1}+f_{j,0}
]
现在问题就是求(f)，大概就是下面几个式子
[f_{i,0}=(1+sum_{j=1}^{i-1}f_{j,0}) imes sum_{j=1}^infty p_i^j
]
[f_{i,1}=(1+sum_{j=1}^{i-1}f_{j,0}) imes sum_{j=1}^infty j imes p_i^j+sum_{j=1}^{i-1}f_{j,1} imes sum_{j=1}^infty p_i^j
]
[f_{i,2}=(1+sum_{j=1}^{i-1}f_{j,0}) imes sum_{j=1}^infty j^2 imes p_i^j+sum_{j=1}^{i-1}f_{j,1} imes sum_{j=1}^infty j imes p_i^j+sum_{j=1}^{i-1}f_{j,2} imes sum_{j=1}^infty p_i^j
]
那几个带着(infty)的式子就是0/1/2阶差比列，错位相减一波有
[sum_{j=1}^infty p_i^j=frac{p_i}{1-p_i},sum_{j=1}^infty j imes p_i^j=frac{p_i}{(1-p_i)^2},sum_{j=1}^infty j^2 imes p_i^j=frac{2p_i}{(1-p_i)^3}-frac{p_i}{(1-p_i)^2}
]