UOJ Logo nealchen2003的博客

博客

标签
暂无

『集训队互测 2021』完结撒花

2021-01-23 21:57:47 By nealchen2003

萌新第一次组织活动,在这里,我首先要感谢 UOJ 的各管理员的付出,感谢各位出题人和选手的参与。

那是在 2020 年 12 月中旬,我的集训队论文才刚刚动笔。写下标题——《#TBA》命题报告。仿着学长 wzt 的命题报告的格式,摘要的第一句话是:“《#TBA》是我为 2021 年集训队互测命制的一道试题。”——等等,互测呢?!

不过考虑到命题报告的明显优势,我选择保持原计划不变。这时我想到,队友 Lagoon 的论文也是命题报告,他的题也没处放。于是我找他商量:要不要办一个比赛放论文题?

两题肯定是不够。不过我想,再团结至少一个人来办起一场比赛,还是不难的。我先获得了集训队教练的批准,然后与 UOJ 取得了联系,开始拉群、发广告、造题。

我们的出题人队伍只有 5 人,Round #1 很顺利地办成之后,我才意识到 Round #2 可能只有两题了。在群里连着两天发广告无人响应,在第三天,我开始对着候选队员名单挨家挨户地征集,却颗粒无收。这期间,zhouzhendongp_b_p_b 先后响应,可惜来稿均被识别出原题,只能作罢。正当此时,幸亏 rushcheyo 站出来,贡献了一道签到题:一番抢救,Round #2 至少成为了一场完整的比赛。

再次地,感谢出题人 EntropyIncreaser, Itst, Lagoon, shiliangzhi, rushcheyo 支持并响应本次活动,贡献了宝贵的一题。

感谢 UOJ 承办本次活动,感谢站长 vfleaking、管理员 mayaohua, rushcheyo, skip2004 的辛勤工作,是他们保障了本次活动顺利举行。值得一提的是,外联大师 rushcheyo 还邀请了国外选手来参赛。

感谢各位选手与我们出题人交流。既然是“互测”,那我们出题人出题目、各位选手解题目,就不是为了选拔选手,而是与选手以攻防战的形式交流。以我命的题《太阳神的宴会》为例,本来我欠思考,武断地认为后缀数组根本做不了,在论文中写:“这种计数问题只能用自动机来表示,痛击了后缀数组的弱点”。所幸,我聆听 djq_cpp, jiangly 等选手的赛后讨论,开始意识到错误。后来 zx2003 提了一个基于后缀数组的做法,时间复杂度是对的,可惜给卡了常数,止步于 81 分(这份代码的提交者是 3002xz)。我的论文中这处严重错误的纠正,离不开各位选手的帮助。

至此,本萌新组织的第一次活动,落下了帷幕。相关题目的资料可能还有不完善的,会尽快补全,维持我们 UOJ 题库的高质量。祝 UOJ 越办越好。

[UR19B]通用测评号 $O(n^2a)$ 另解

2020-04-05 20:52:21 By nealchen2003

萌新第一次发博,不知道和出题人的Bonus做法是否相同。提交时是速度第一名,后来被一个内存比我小很多的做法吊锤了。

题意简述

有 $n$ 个数,初始都是 $0$, 每次随机一个小于 $a$ 的数将其加上 $1$, 当且仅当所有数都不小于 $b$ 时结束。求 $a$ 的个数的期望。

限制:$n \le 250, 1 \le b < a \le 250$.

我的想法

最后一步操作一定是把 $b-1$ 变成 $b$. 我把这一步叫做终止操作。与终止操作对象相同的其余 $b-1$ 次操作叫做终止操作的相关操作

考虑影响操作序列的取得概率的步骤,是把 $a-1$ 变成 $a$. 我把这一步叫做加满操作。与一个加满操作的对象相同的其余 $a-1$ 次操作叫做它的相关操作

如果一个操作不属于终止操作、加满操作或是它们的相关操作,这个操作就叫做普通操作

考虑按照时间加入加满操作,顺便维护其相关操作和在其之前的普通操作。有些操作可能是后续加满操作或终止操作的相关操作,但是在后续操作加进来之前,我们仍然把它视为普通操作。

记 $g(i, j)$ 表示放入前 $i$ 个加满操作,在第 $i$ 个加满操作之前有 $j$ 个普通操作,所有满足此情况的状态取得的概率和。

初值:$g(0, 0)=1$.

转移:设第 $i-1$ 个加满操作和第 $i$ 个加满操作之间有 $k$ 个操作,连带加满操作一共需要在概率中乘上 $(n-i+1)^{-k-1}$; 这个加满操作的对象有 $n-i+1$ 种可能性;在 $j+a-1$ 个普通操作中需要确定 $a-1$ 个第 $i$ 个加满操作的相关操作。于是转移为

$$g(i, j)=\sum_{k=0}^{j+a-1}\binom{j+a-1}{a-1}g(i-1, j+a-1-k)(n-i+1)^{-k}$$

最后还需要放入一个终止操作,和上述转移基本类似,只是把 $a$ 改成了 $b$. 假设结束时,放了 $i$ 个加满操作,还剩余 $j$ 个普通操作,所有如此的操作序列的概率和记为 $h(i, j)$.

接下来还剩下 $n-i-1$ 个最终落于区间 $[b, a)$ 内的整数。设 $f(i, j)$ 表示 $j$ 个普通操作分配给 $i$ 个对象,使得每个对象都操作了不少于 $b$ 次但少于 $a$ 次的方案数。

初值:$f(0, 0)=1$.

转移:$f(i, j)=\sum_{k=b}^{a-1}\binom jkf(i-1, j-k)$

所以所有含恰好 $i$ 个 $a$ 的终止态的概率之和是 $P_i=\sum_{j=0}^{na}f(n-i-1, j)h(i, j)$.

那么在操作已终止的前提下其概率就是 ${P_i \over \sum_{k=0}^{n-1}P_k}$. 答案即 $\sum_{i=0}^{n-1}iP_i$.

场上想到的优化

把 $f$ 写成生成函数的形式,有 $\sum_{j=0}^{na}{f(i, j) \over j!}x^j=\left(\sum_{k=b}^{a-1}{x^k \over k!}\right)^i$

把 $g$ 的转移也写成生成函数的形式,有 $g(i, j)=[x^{j+a-1}]\binom{j+a-1}{a-1}\left(\sum_{j=0}^{na}g(i-1, j)x^j\right)\left(\sum_{k=0}^{na}(n-i+1)^{-k}x^k\right)$

于是两个都用NTT算一算,复杂度 $O(n^2a\log(na))$, 常数巨大,只能拿 $70$ 分。

场后想到的优化

鬼知道我场上脑子里堆了多少铁锈。首先我们发现

$$\begin{align}g(i, j)&=[x^{j+a-1}]\binom{j+a-1}{a-1}\left(\sum_{j=0}^{na}g(i-1, j)x^j\right)\left(\sum_{k=0}^{na}(n-i+1)^{-k}x^k\right)\\&=[x^{j+a-1}]\binom{j+a-1}{a-1}\frac{\sum_{j=0}^{na}g(i-1, j)x^j}{1-{x \over n-i+1}}\end{align}$$

用暴力除,即可减少 $3n$ 次NTT(我场上的做法甚至比这多做了 $6n$ 次),估计就 A 了吧。

接下来的内容感谢 EntropyIncreaser 教育。

设 $F=\sum_{k=b}^{a-1}{x^k \over k!}$, 那么 $F'=F-G$, 其中 $G={x^{a-1} \over (a-1)!}-{x^{b-1} \over (b-1)!}$.

那么 $(F^i)'=iF^{i-1}F'=iF^i-iGF^{i-1}$, 移项可得 $F^i-{(F^i)' \over i}=GF^{i-1}$, 从高到低确定位即可。

于是整个做法的时间是 $O(n^2a)$, 空间由于需要完整保存 $f, g$ 其中任意一个,也为 $O(n^2a)$.

共 2 篇博客