当前位置: 首页 > news >正文

CF1667E Centroid Probabilities

题目描述

对于所有点数为 nnn 的树,如果其满足 对于所有 i∈[2,n]i\in [2,n]i[2,n],与 iii 相连的 jjj 中有且只有一个点 jjj 满足 j<ij<ij<i ,那么我们称其为好树

对于 1∼n1\sim n1n 每个点求出来有多少好树满足重心为 iii

这里重心定义为删去这个点后形成的所有连通块大小均小于 n−12\frac{n-1}22n1

数据范围 3≤n≤2×1053\le n\le 2\times 10^53n2×105nnn 为奇数(所以不存在树有多个重心的情况)

题解

m=n+12m=\frac{n+1}{2}m=2n+1fif_ifi表示iii的子树大小≥m\ge mm的方案数
枚举iii的子树大小jjj,则有式子
fi=(i−1)∑j=mn−i+1(n−ij−1)(j−1)!(n−j−1)!f_i=(i-1)\sum_{j=m}^{n-i+1}\binom{n-i}{j-1}(j-1)!(n-j-1)!fi=(i1)j=mni+1(j1ni)(j1)!(nj1)!
前面的i−1i-1i1是钦定iii的父亲,组合数是从iii后面的点中选出属于iii子树的点,两个阶乘是为了计算两个点集连成树的方案数
=(i−1)∑j=mn−i+1(n−i)!(j−1)!(n−i−j+1)!(j−1)!(n−j−1)!=(i-1)\sum_{j=m}^{n-i+1}\frac{(n-i)!}{(j-1)!(n-i-j+1)!}(j-1)!(n-j-1)!=(i1)j=mni+1(j1)!(nij+1)!(ni)!(j1)!(nj1)!

=(i−1)(n−i)!∑j=mn−i+1(n−j−1)!(n−i−j+1)!=(i-1)(n-i)!\sum_{j=m}^{n-i+1}\frac{(n-j-1)!}{(n-i-j+1)!}=(i1)(ni)!j=mni+1(nij+1)!(nj1)!

=(n−i)!(i−1)!∑j=mn−i+1(n−j−1)!(n−i−j+1)!(i−2)!=(n-i)!(i-1)!\sum_{j=m}^{n-i+1}\frac{(n-j-1)!}{(n-i-j+1)!(i-2)!}=(ni)!(i1)!j=mni+1(nij+1)!(i2)!(nj1)!

=(n−i)!(i−1)!∑j=mn−i+1(n−j−1i−2)=(n-i)!(i-1)!\sum_{j=m}^{n-i+1}\binom{n-j-1}{i-2}=(ni)!(i1)!j=mni+1(i2nj1)

=(n−i)!(i−1)!∑k=i−2n−m−1(ki−2)=(n-i)!(i-1)!\sum_{k=i-2}^{n-m-1}\binom{k}{i-2}=(ni)!(i1)!k=i2nm1(i2k)

=(n−i)!(i−1)!(n−mi−1)=(n-i)!(i-1)!\binom{n-m}{i-1}=(ni)!(i1)!(i1nm)

于是fif_ifi可以O(n)O(n)O(n)计算,考虑容斥求出ansians_iansi表示以iii为重心的方案数,枚举它的儿子jjj子树大小≥m\ge mm,显然对于jjj来说父亲为哪个方案数都是一样的,所以以iii为父亲的方案数就是fjj−1\frac{f_j}{j-1}j1fj,即答案为ansi=fi−∑j=i+1fjj−1ans_i=f_i-\sum_{j=i+1}\frac{f_j}{j-1}ansi=fij=i+1j1fj

code\text{code}code

#include<cstdio>
#define ll long long
using namespace std;
const ll mod=998244353;
ll ksm(ll a,ll b)
{if(b==0) return 1;ll tmp=ksm(a,b>>1);if(b&1) return tmp*tmp%mod*a%mod;else return tmp*tmp%mod;
}
const int N=2e5+1000;
int n;
ll f[N+10],fac[N+10],inv[N+10];
ll C(int n,int m){if(m>n) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{scanf("%d",&n);fac[0]=inv[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,inv[i]=ksm(fac[i],mod-2);f[1]=fac[n-1];int m=n+1>>1;for(int i=2;i<=n;i++) f[i]=fac[i-1]*fac[n-i]%mod*C(n-m,i-1)%mod;ll res=0;for(int i=n;i>=1;i--){ll tmp=f[i];f[i]=(f[i]+mod-res)%mod;res+=tmp*ksm(i-1,mod-2)%mod,res%=mod;}for(int i=1;i<=n;i++) printf("%lld ",f[i]);puts("");return 0;
}
http://www.lryc.cn/news/7048.html

相关文章:

  • 全网详细总结com.alibaba.fastjson.JSONException: syntax error, position at xxx常见错误方式
  • 快速部署个人导航页:美好的一天从井然有序开始
  • 【Python】如何在 Python 中使用“柯里化”编写干净且可重用的代码
  • ROS笔记(4)——发布者Publisher与订阅者Subscribe的编程实现
  • Linux进程概念(一)
  • Leetcode.1124 表现良好的最长时间段
  • 达梦数据库会话、事务阻塞排查步骤
  • sqlServer 2019 开发版(Developer)下载及安装
  • 使用Arthas定位问题
  • 性能测试之tomcat+nginx负载均衡
  • 【手写 Vuex 源码】第十一篇 - Vuex 插件的开发
  • opencv基础知识和绘图图形
  • 15- 决策回归树, 随机森林, 极限森林 (决策树优化) (算法)
  • Flink相关的记录
  • 配置可视化-基于form-render的无代码配置服务(一)
  • Java 代理模式详解
  • 知识付费小程序怎么做_分享知识付费小程序的作用
  • 14- 决策树算法 (有监督学习) (算法)
  • 如何编译和运行C++程序?
  • Golang 给视频添加背景音乐 | Golang工具
  • 让AI护理医疗:解决卫生系统的痛点
  • Windows 离线安装 MySQL 8
  • 【前端攻城狮之vue基础】02路由+嵌套路由+路由query/params传参+路由props配置+replace属性+编程式路由导航+缓存路由组件
  • CHAPTER 1 Zabbix介绍及安装
  • 认识V模型、W模型、H模型
  • excel ttest检测
  • PDFPrinting.Net操作进行细粒度控制
  • SegPGD
  • ESP-IDF + Vscode ESP32 开发环境搭建以及开发入门
  • SpringMvc的请求和响应