首页 > 其他分享 >YC322A [ 20240724 CQYC NOIP 模拟赛 T4 ] 庫的 序计数(counting)

YC322A [ 20240724 CQYC NOIP 模拟赛 T4 ] 庫的 序计数(counting)

时间:2024-07-24 22:09:21浏览次数:15  
标签:线段 YC322A NOIP siz T4 texttt times 次数 节点

题意

给定一棵树 \(T\),每次操作在某个点下方接上 \(k\) 个儿子。

询问期望多少次排列,使得 \(a_{fa_i} < a_i\)。

保证 \(k\) 是偶数,对 \(65536\) 取模。

\(n \le 10 ^ 5, k \le 2 \times 10 ^ 9\)。

Sol

考虑假如已经确定了一棵树的形态,如何求出最终的答案?

可以发现对于每一个节点考虑,她需要满足她在排列中的位置在她所有的子节点的前面。

所以每一个点满足限制的概率是 \(\frac{1}{siz_i}\) 的。

由于独立事件,期望为概率的倒数。

所以答案就是 \(\prod siz_i\)。

考察如何动态维护一棵树的 \(siz\)。

套路地,将询问离线下来,只考虑使用过的节点,建出类似虚树的东西。

现在每次操作变为在虚树上一条根到节点的链加,最后求所有 \(siz\) 的乘积。

这很明显是没法做的。

集中注意力,思考一些厉害的东西。把每个节点拆成 \((x + siz)\) 的形式,这样将所有点乘起来会变成一个长度为 \(n\) 的 \(\texttt{Poly}\),然后链加就变成 \(a_i \times (x + k)\) 的形式,最后把所有的 \(\texttt{Poly}\) 乘起来,答案就是次数为 \(0\) 的系数。

注意到模数就是 \(2 ^ {16}\),结合 \(2 | k\),发现一个很厉害的事情,我们只需要维护次数为 \([0, 15]\) 的系数就可以了,因为 \(2 | k\),对于次数 \(\le 16\) 的点,她一定不会对次数为 \(0\) 的点产生贡献,并且,假设当前点 \(i, i \ge 16\) 对 \([1, 15]\) 的点产生了贡献 \((2 \times p) ^ {i - j}\),可以发现次数为 \(i - j\) 的这个点再贡献一步到 \(0\),显然需要 \((2 \times p) ^ {j}\) 的贡献,这和之前的乘起来刚好就是 \((2 \times p) ^ i\),所以还是不对次数为 \(0\) 的点产生贡献。

至此做法已经十分显然了,对于线段树上每个节点维护长度为 \([0, 15]\) 的 \(\texttt{Poly}\),然后线段树在合并的时候就暴力乘,加 \(k\) 就直接用二项式定理暴力拆出来。

最后加上树剖的复杂度一共是 \(\log ^ 4\) 的,很难通过。

可以考虑把树剖+线段树换成 \(\texttt{lct}\),或者注意到查询时间复杂度为 \(O(1)\),直接开 \(n\) 颗线段树维护树剖上所有的链,这样都是 \(\log ^ 3\) 的。

标签:线段,YC322A,NOIP,siz,T4,texttt,times,次数,节点
From: https://www.cnblogs.com/cxqghzj/p/18321862

相关文章

  • VS2022 安装.NET4.5目标包
    转载自https://www.cnblogs.com/Stay627/p/15549958.html[VS2022安装.NET4.5目标包]众所周知VS2022将不再支持.NET4.5,即使在VisualStudioInstaller中也找不到.NET4.5的选项在不改变项目结构的情况下,要么选择继续使用VS2019,当然博主已经卸掉了,那么还有什么方法呢?我们可以......
  • YC322A [ 20240724 CQYC NOIP 模拟赛 T3 ] 小 M 的字符串(string)
    题意给定一个\(0/1\)字符串,你需要从中选出尽可能多的不相交的子串使得按顺序字典序单调递增。\(n\le25000\)。Sol先考虑能最多选出多少个不相交的子串,这个是\(\frac{n}{\logn}\),但是这个没用。考察一下子串的长度,由于字典序的限制,最劣的情况下就是一个子串比上一个子串......
  • 将 TradingView 电子邮件信号连接至 MT4
    我对编码了解不多,但我尝试进行一些研究。我想在MT4上启用TradingView电子邮件信号,但尽管正在阅读电子邮件,但它们并未在MT4上执行。如果您能帮助我,我将非常高兴。importimaplibimportemailimportzmqimportrandomimportdatetime,timefromemail.headerimport......
  • DeepSpeed x MiniGPT4Qwen
    #关于DeepSpeed的尝试知乎博客地址:https://zhuanlan.zhihu.com/p/673359684##参考Repo:https://github.com/microsoft/DeepSpeedExampleshttps://github.com/microsoft/DeepSpeedExamples/blob/master/training/HelloDeepSpeed/train_bert_ds.py,代码拷贝到了本项目的:htt......
  • P3957[NOIP2017普及组]跳房子
    https://www.luogu.com.cn/problem/P3957https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337显然,但是维护滑动窗口有技巧,不能每次插入一个值,因为维护\(x\)不方便。所以考虑一个\(cur\),每次对于新的\(i\)不能跳过时移动\(cur\),然后队......
  • 洛谷P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    [NOIP2001普及组]最大公约数和最小公倍数问题题目描述洛谷题目链接:https://www.luogu.com.cn/problem/P1029输入两个正整数x,y,求出满足下列条件的P,Q的个数:P,Q是正整数。要求P,Q以x为最大公约数,以y为最小公倍数。试求:满足条件的所有可能的P,Q的个数。......
  • qaq(曾经の NOIP 模考)
    TomoyukiMIzuyama要出\(n\)道题,他现在有\(m\)个不同的乱码,他非常的阴间,所以他决定先决定先用这群乱码起好第一个题目的名字,之后每个题目都直接从上一个题目名字中找一个子序列当做自己的名字。现在他想知道,在第\(i\)道题目名字长度为\(a_i\)的情况下(\(a_1\gea_2\ge\cd......
  • xfs-2024-NOIP模拟赛
    0722模拟赛这是计数专场吗,把我秒掉了。难原:P7050[NWRRC2015]Concatenation给定两个字符串a,b,从a中选一段前缀,b中选一段后缀(前后缀都可以为空),并将选出的后缀拼在选出的前缀后面。你需要求出有多少种本质不同的串(可以为空)。思路总方案数减去不合法的方案数。以ab......
  • [NOIP2008 提高组] 笨小猴(洛谷题号P1125)
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的......
  • [NOIP2012 普及组] 摆花(含代码)
    [NOIP2012普及组]摆花题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共mmm盆。通过调查顾客的喜好,小明列出了顾客最喜欢的......