2021年8月模拟赛简要题解·下

人世几回伤往事，山形依旧枕寒流。

2021.08.17

A.魔力

魔力

设 $cnt_i$ 为字符 $i$ 出现的次数，那么题目求的就是所有 $cnt_i$ 均相等的区间个数

因为 $cnt_i$ 不固定，所以做个差分可以发现当且仅当差分为 $0$ 的时候合法

那么从 $1$ 开始拓展记录 $cnt$ 差分，如果出现了两个地方的 $cnt$ 差分数组相同，那么这两个 $cnt$ 差分数组相减就是全 $0$

记录一个 vector 的 map 即可

code

B.粒子

粒子

就是一大堆一次函数求第一次交点

二分时间即可

code

C.六

六

状压

发现只压某个质因子出现的次数是不行的

因为 $(2,3)$ $(6)$ 质因子出现次数相同，但是可以转移的状态不同

还需要记录一个每一对质因子能否同时出现在一个数里的状态

这里只需要二进制 $\dfrac{cnt(cnt-1)}{2}$ 位，质因子是三进制状压

记录一个 pair 去转移即可

考的时候没想到再去记录一个二进制位

code

D.多重集合问题

多重集合问题

经典题目，整体二分

code

2021.08.18

A.引子

引子

大模拟，注意数字可以是多位数

code

B.可爱精灵宝贝

可爱精灵宝贝

记录 $dp_{l,r,t,0/1}$ 表示拿完 $[l,r]$ 的物品后时间为 $t$ 且在左/右端点上的最大价值

分类讨论转移

code

C.相互再归的鹅妈妈

相互再归的鹅妈妈

钦定有些人能选同一个然后斯特林反演

不会写

D.盟誓的文艺复兴

盟誓的文艺复兴

首先注意到只有 $c=2,3$ 是有意义的，别的都可以拆成 $c=2.3$ 的情况

$c=2$ 的情况就是

$\sum\limits_{i=1}^{\sqrt[3]{n}} \mu^2(i)(\sqrt{\dfrac{n}{i}}-i)$

即枚举无完全平方因子的数，然后乘上能选的数字 ( $a<b$ )

$c=3$ 比较复杂

先把 $c=2$ 统计过的排除掉

设 $k$ 是满足 $k^2 | ab$ 最大数字

那么 $ab^3 = (\dfrac{ab}{k^2})(bk)^2$

考虑如果之前没被统计过需要满足 $\dfrac{ab}{k^2}>bk \Rightarrow a \ge k^3$

定义 $\mu_3(x) := [\not\exist d^3|x,d\neq 1]$

即没有完全三次方因子

式子是

$\huge\sum\limits_{a=1}^{\sqrt[4]{n}}\mu_3(i)\sum\limits_{k^3\le a}\sum\limits_{b=a+1}^{\sqrt[3]{\frac{n}{a}}}[k^2|ab]\mu^2(\dfrac{ab}{k^2})$

然后设 $g=\gcd(a,k^2),a'=\dfrac{a}{g},k'=\dfrac{k^2}{g},b'=\dfrac{b}{k'}$ （神奇代换，不懂原理）

$\huge\sum\limits_{a=1}^{\sqrt[4]{n}}\mu_3(i)\sum\limits_{k^3\le a}\sum\limits_{b'=\frac{a}{k'}+1}^{\frac{\sqrt[3]{\frac{n}{a}}}{k'}}\mu^2(a'b')$

$\mu(ab)= \mu(a)\mu(b)[\gcd(a,b)=1]$

所以

$\huge\sum\limits_{a=1}^{\sqrt[4]{n}}\mu_3(i)\sum\limits_{k^3\le a}\mu^2(a')\sum\limits_{b'=\frac{a}{k'}+1}^{\frac{\sqrt[3]{\frac{n}{a}}}{k'}}\mu^2(b')[\gcd(a',b')=1]$

反演掉 $[\gcd(a,b)=1]$

$\huge\sum\limits_{a=1}^{\sqrt[4]{n}}\mu_3(i)\sum\limits_{k^3\le a}\mu^2(a')\sum\limits_{d|a'}\mu(d)\sum\limits_{b'=\frac{a}{k'}+1}^{\frac{\sqrt[3]{\frac{n}{a}}}{k'}}[d|b']\mu^2(b')$