拆贡献+统计非法可能不统计非法贡献：ARC150D
拆贡献+统计非法可能不统计非法贡献：ARC150D
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134047357
https://atcoder.jp/contests/arc150/tasks/arc150_d
先拆贡献成每个点，然后就只需要考虑这条链上的情况了
我们现在要求的是：
- 在所有点选完之前，最后一个点被选了多少次
我们发现这很难做，但有个性质：
-
在所有点选完前，最后一个点始终是坏点
-
因此我们可以钦定好点也可以选，只是不计算其贡献
而计算所有点被选的期望次数是 ，选中最后一个点的期望次数是
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-06
次方计数的拆贡献法（考虑组合意义）+限定类问题善用值域与位置进行ds：1006T3
次方计数的拆贡献法（考虑组合意义）+限定类问题善用值域与位置进行ds：1006T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133621275 对于多次方的计数问题可以考虑拆贡献。 题目问 ∣S∣3|S|^3∣S∣3 ， ∣S∣|S|∣S∣ 表示选的点数。相当于在 ∣S∣|S|∣S∣ 中选了3次，也就是选了3个可相同的点。 先考虑3个不相同点的贡献，对应任意3个点，必然会对所有包含其矩形产生贡献。所以只需要统计对应的矩形数目。但是必须乘上全排列6，因为...
2023-09-27
拆贡献与期望本质：CF1392H
拆贡献与期望本质：CF1392H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133355060 题目问牌数，但其实题面有另一个很明显的东西叫轮数 而如果我们每一轮单独考虑，其对应的期望牌数是确定的。 我们肯定会大胆考虑直接用期望牌数乘期望轮数，但为什么对？ 每轮牌数乘上前 i−1i-1i−1 轮未结束的的概率，后面的概率是第 iii 轮恰好结束的前缀和，而我们再求个和就是期望轮数。 考虑每一轮的期望牌数。首先肯定会抽到一种鬼牌，所以必然+1。然后考虑经典...
2024-08-20
8.20T1 星图（拆贡献+DP+暴力卷积）
8.20T1 星图（拆贡献+dp+暴力卷积） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141361722 http://cplusoj.com/d/senior/p/NODSX2301A 给定 nnn 个实数的取值范围，求其笛卡尔树节点深度总和的期望。 场上搞了一大轮区间dp，结果大方向就错了。 拆贡献，考虑 jjj 对 iii 是否有贡献。若 jjj 对 iii 有贡献，则 jjj 是 iii 的祖先，此时贡献为1。所以我们只需要计算 jjj ...
2023-10-10
期望+拆贡献+充斥：CF1349D
期望+拆贡献+充斥：CF1349D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187 第一步：找性质 每个人的期望步数只与总数量 mmm ，总人数 nnn ，自己数量 aia_iai 有关 第二步：转化（难点） 拆贡献：拆成每个人win的期望步数，然后求 ∑E(i)\sum E(i)∑E(i) 容斥：肯定不能直接算。于是考虑算直到第 iii 个人拿完才结束的的期望步数 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， ...
2023-10-09
质因子拆贡献+朴素容斥：1007T3
质因子拆贡献+朴素容斥：1007T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133697910 http://cplusoj.com/d/senior/p/SS231007C 考虑枚举gcd，然后容斥，恰好转至少。 ggg 表示gcd恰好为 ddd ， fff 表示至少为 ddd 显然有 f(d)=∑d∣ng(n)f(d)=\sum_{d|n}g(n)f(d)=∑d∣ng(n) ，可以直接莫反成： g(d)=∑d∣nf(n)μ(nd)g(d)=\s...
2024-10-07
1007C步行（树上贡献统计）
1007C步行（树上贡献统计） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142742718 http://cplusoj.com/d/senior/p/SS241007C 首先可以发现每条边的贡献为 2min(wx,S−wx)2\min(w_x,S-w_x)2min(wx,S−wx) ， xxx 为下端的点 考虑现在断一条边，连一条边。我们先不考虑断边，只连边。那么这是一个基环树，不在环上的贡献使容易算的 对于这个环，我们要先找出它的 www 变...