我们需要理解变换的本质从而不会像个煞笔一样给自己增添不必要的复杂度。 Description Claris 和 NanoApe 在玩石子游戏,他们有 $n$ 堆石子,规则如下: Claris 和 NanoApe 两个人轮流拿石子,C...
快速沃尔什变换 FWT 学习笔记【多项式】
〇、前言 之前看到异或就担心是 FWT,然后才开始想别的。 这次学了 FWT 以后,以后判断应该就很快了吧? 参考资料 FWT 详解 知识点 by neither_nor 集训队论文 2015 集合幂级数的性质与应用及其快速算法 by ...
fread 相关快速读入 学习笔记【语言】
〇、前言 之前在浙江集训的时候,有一道 $n\le 3\times 10^6$ 的题,解题复杂度是 $O(n\alpha(n))$ 的,但是我丑得要命的大概是 $O(n\log n)$ 的 read() 被卡掉了。_(:з」∠)_ 后来用了 fread() 的黑科...
CF1152E Neko and Flashback 题解【欧拉路】【构造】
这种找可行解的问题套路还是比较多的。 Description A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $...
ZJOI 2019 Day2 游不动记
Day 1 在余姚中学待了一周多,还没去看过五楼报告厅。报告厅还是比较宽敞的,还有 LED 屏幕。 上午是 zzy 讲《树上分治算法》,分别讲了边分、点分和全局平衡二叉树。讲的很快,例题引入比较跳跃于是成功在开场...
2019.4 余姚中学 被吊打记
$\TeX$ 版游记 (不好意思标题有点不恰当别人貌似不屑于吊打我) Day -1 第一次坐软卧,感觉空间宽敞,设施也比较新。当然是多交钱了的 Day 0 早上 8 点到了余姚站,坐了十几分钟公交车到宾馆。误判了地图的...
bzoj 4176 Lucas的数论 题解【莫比乌斯反演】【杜教筛】
怎么又有我不知道的东西啊..自闭了 Description 去年的 Lucas 非常喜欢数论题,但是一年以后的 Lucas 却不那么喜欢了。 在整理以前的试题时,发现了这样一道题目“求 $\sum f(i)$,其中 $1\le i\le ...
洛谷 P3327 [SDOI2015]约数个数和 题解【莫比乌斯反演】【前缀和】【质因数分解】
有个引理。希望以后这种东西还是能自己推出来 题目描述 设 $d(x)$ 表示 $x$ 的约数个数,给定 $N,M$,求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$。 输入输出格式 输入格式: 输入文件包含多组...
杜教筛瞎推 学习笔记【杜教筛】【数学】
〇、前言 对于 bzoj3944 来说,和莫比乌斯反演等其他知识关系不大,但是 $\mu$ 函数在自变量较大情况下的前缀和在反演题中也是会被用到的。 接下来通过 bzoj3944 Sum 一题引入杜教筛的思想。 参考资料 铃悬...
HBTS(HBOI) 2019 真实退役记
Day 0 早上迷迷糊糊醒了不知道多久,反正差不多的时间被叫醒了,然后走去了火车站。 这次终于取到了蓝色的车票,以前去武汉的车票都取的红色不知道为什么…… 在火车上看了《悲伤逆流成河》,稍微有点悲情,还...