杭州建设项目审批网站,wordpress 服务器配置,数据库修改wordpress文章浏览量,软件下载网站排行榜前十名正题
题目链接:https://www.luogu.com.cn/problem/P4492 题目大意
开始有一个节点#xff0c;第iii次在一个儿子不超过222的节点下面长出一个新儿子编号为iii。求所有方案下树的路径长度和。 解题思路
考虑计算每条边的贡献#xff0c;设gig_igi表示大小为iii的树的形态…正题
题目链接:https://www.luogu.com.cn/problem/P4492 题目大意
开始有一个节点第iii次在一个儿子不超过222的节点下面长出一个新儿子编号为iii。求所有方案下树的路径长度和。 解题思路
考虑计算每条边的贡献设gig_igi表示大小为iii的树的形态个数fif_ifi表示所有大小为iii的树的路径长度和。然后题目给出的要求就是子节点编号比父节点大。
那么ggg有转移gi1∑j0igjgi−jCijg_{i1}\sum_{j0}^ig_jg_{i-j}C_{i}^jgi1j0∑igjgi−jCij fff的转移复杂一点枚举子树大小jjj和i−ji-ji−j那么子树jjj自己的贡献就是gj∗j∗(n−j)g_j*j*(n-j)gj∗j∗(n−j)然后要乘上gi−jg_{i-j}gi−j表示每种左子树形态对应的树的形态个数。右边i−ji-ji−j同理就有转移方程fi1∑j0i(gigj(j∗(n−j)(i−j)∗(n−ij))fj∗gi−jfi−j∗gj)∗Cijf_{i1}\sum_{j0}^i(\ g_ig_j(j*(n-j)(i-j)*(n-ij))f_j*g_{i-j}f_{i-j}*g_j\ )*C_{i}^jfi1j0∑i( gigj(j∗(n−j)(i−j)∗(n−ij))fj∗gi−jfi−j∗gj )∗Cij
时间复杂度O(n2)O(n^2)O(n2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100;
ll n,p,f[N],g[N],c[N][N];
int main()
{scanf(%lld%lld,n,p);g[0]c[0][0]1;for(ll i1;in;i)for(ll j0;ji;j)c[i][j]((j?c[i-1][j-1]:0)c[i-1][j])%p;for(ll i0;in;i){for(ll j0;ji;j){(g[i1]g[j]*g[i-j]%p*c[i][j])%p;(f[i1](((i-j)*(n-ij)%pj*(n-j)%p)*g[j]%p*g[i-j]%pf[j]*g[i-j]%pf[i-j]*g[j]%p)%p*c[i][j]%p)%p;}}printf(%lld\n,f[n]);return 0;
}
