2
wlzhouzhuan
·
·
个人记录
F - One Third
考虑将每一刀的半径标记红色，逆时针方向 120° 的半径标记蓝色，顺时针 120° 的半径标记绿色，则 |x-\frac 13| 的最小值转化为相邻异色半径夹角的最小值（还要除以 360° ）。
不妨将第一刀的半径记为 0° ，不难发现只需保留 0° 到 120° 的半径，其余两部分与此部分答案等价，无需考虑。
问题转化为：在一个数轴上，一开始在 0 和 \frac 1 3 处分别有一个红点和蓝点，然后在 [0,\frac 13] 中随机撒 n-1 个随机颜色（红、蓝、绿）点，求异色点距离最小值的期望是多少。
记 f(k) 表示恰好 k 对相邻异色点的概率， g(k) 表示恰好 k 对相邻异色点时距离最小值的期望，则答案为 \sum\limits_{k}f(k)g(k) 。
用 $dp[i]$ 表示有 $i+1$ 段的答案，则有 $dp[i]=dp[i-1]+2dp[i-2]$ ，其中 $dp[1]=1,dp[2]=1$ 。
因此 $f(k)=\frac{\binom{n}{k}dp[k]}{3^{n-1}}
$$\int_0^\frac{1}{k}(1-kt)^{k-1}dt=\frac{1}{k}\int_0^1(1-t)^{k-1}dt=\frac{1}{k}\int_0^1t^{k-1}dt=\frac{1}{k^2}$$
时间复杂度 $O(n)$ 。
## F - Walk On Graph
**Solution**
将路径翻转，则每经过一条边权 $c$ 的边，权值从 $x$ 到 $2x+c$ 。记状态 $(u,x)$ 表示在点 $u$ 权值为 $x$ 。
令 $f(x)=2x+c$ ，由于 $p$ 是奇数，所以 $2$ 有逆元，故 $f$ 是一个置换（双射），必存在置换环，故 $(u,x)$ 和 $(v,2x+c)$ 互相可达。
若存在 $(u,v,a),(u,w,b)$ 则 $(u,x),(v,2x+a),(u,4x+3a)$ 可达且 $(u,x),(w,2x+b),(u,4x+3b)$ 可达，故 $(u,x+3g)$ 均可达，因为图是连通的，所以 $g=gcd(\text{相邻边权差})$。
因此可将 $p$ 视作 $gcd(p,3g)$ 。
令 $z=\text{边权} \%p$ ，将所有边权 $c$ 变为 $c-z$ ，则 $(u,x)$ 变为 $(u,x+z)$ 。可以发现，$(v,2(x+z)+c-z)=(v,2x+c+z)$ 依然正确。
于是 $(u,x)$ 出发能到达的状态能表示为 $(u,2^px+qg)$ 的形式，其中 $q$ 可对 $3$ 取模。
因为 $(u,x),(v,2x+c),(u,4x+3c)=(u,4x)$ ，所以 $2^p$ 也可对 $3$ 取模，相应的 $p$ 对 $2$ 取模。
故只需预处理连通性即可，对于每个点拆成 $6$ 个点，表示 $\mathrm{p=0/1,q=0/1/2}$ 的情形。
时间复杂度 $O(n)$ 。
## ULR-1 校验码
显然有 $f(d^2n)=d^cf(n)$ 。
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(ij)$$
枚举非平方因子：
$$=\sum_{i=1}^{n}\mu^2(i)\sum_{p^2i\le n}p^c\sum_{j=1}^{m}\mu^2(j)\sum_{q^2j\le m}q^cf(ij)$$
记 $S(n)=\sum\limits_{i=1}^{n}i^c$ ：
$$=\sum_{i=1}^{n}\mu^2(i)S\left(\sqrt{\frac{n}{i}}\right)\sum_{j=1}^{m}\mu^2(j)S\left(\sqrt{\frac{m}{j}}\right)gcd(i,j)^c$$
令 $g=\mu * ID_c$ ，则 $ID_c=g * I$ ，代入：
$$=\sum_{i=1}^{n}\mu^2(i)S\left(\sqrt{\frac{n}{i}}\right)\sum_{j=1}^{m}\mu^2(j)S\left(\sqrt{\frac{m}{j}}\right)\sum_{d|gcd(i,j)}g(d)$$
$$=\sum_{d=1}^{n}g(d)\sum_{i=1}^{n/d}\mu^2(id)S\left(\sqrt{\frac{n}{id}}\right)\sum_{j=1}^{m/d}\mu^2(jd)S\left(\sqrt{\frac{m}{jd}}\right)$$
令 $H(n,d)=\sum\limits_{i=1}^{n}\mu^2(id)S(\sqrt{\frac ni})$ ，则：
$$=\sum_{d=1}^{n}g(d)H(\frac{n}{d},d)H(\frac{m}{d},d)$$
$\color{white}{iakioi}
会发现 n 是 O(\sqrt{m}) 量级的，所以暴力预处理即可。
g(n)=\sum_{i|n}\mu(\frac ni)i^c
会发现 n 是 O(N) 量级的，暴力预处理即可。复杂度 O(nlogn) 。
对于 d=1 ：
H(n,1)=\sum_{i=1}^{n}\mu^2(i)S(\sqrt{\frac ni})
当 i\le n^{1/3} ，显然有 O(n^{1/3}) 种取值；
当 i>n^{1/3} ，\sqrt{\frac ni}\le n^{1/3} ，依旧有 O(n^{1/3}) 种取值。
并且有 \sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{n}\mu(i)\lfloor \frac{n}{i^2}\rfloor ，做法同上。
对于 d>1 ：
H(n,d)=\mu^2(d)\sum_{i=1}^{n}\mu^2(i)S\left(\frac{n}{i}\right)\sum_{e|gcd(i,d)}\mu(e)
=\mu^2(d)\sum_{e|d}\mu(e)H(\frac ne,e)
递归下去即可。
[正睿日报#2] 正睿OI蔡老板经验谈：该如何学习，才能成为信奥大鸟？
前几天，2021年全国青少年信息学奥林匹克冬令营顺利举办，从国家集训队队员中选出4人进入国家队，代表中国参加国际比赛。
信息学说起来挺高端，但实际上，每个家庭只要有电脑，都有机会接触到。
信息学竞赛，主要考察计算机程序设计能力，即编程，很多题目是为了解决生活中的实际问题。比如一次竞赛出题：N个人到一家饭店吃饭，每人点一道菜。饭店有M个厨师，每位厨师做每道菜都消耗不同时间。现在由你来安排厨师做菜，要求让所有人的等待时间之和，越短越好。
在讨论信息学人才培养与IT产业发展时，正睿OI的蔡老板举了个例子来说明两者的关系：
“三个月前，我去美国硅谷出差，和一名在谷歌公司工作的学生相约见面。到了谷歌，却见到我的十多名学生，他们都在那里工作，而且之前全都是参加信息学竞赛的队员。谷歌这种全球顶级的IT公司，很看重大家在竞赛中逐渐形成的分析问题、解决问题的能力。”
这可不是瞎吹，蔡老板在赛前点名道姓4位最有希望成为国家队的选手，最后奶中3名选手，属实OI行业中的大满贯老板。
图来自QQ群
正睿OI的蔡老板，带了竞赛十几年，教出不少学生获得国际金牌，被国内外顶尖高校录取。他为人谦逊，态度端正。培养出来的学子积极向上，后在谷歌、微软等工作。