Qiuly

成都石室划水游记
Day 0早上起得很早精力不好。到了火车站,排队的时候在队伍中换个位置,后面的一堆中年女士一下子就沸腾了到处喷我插...
扫描右侧二维码阅读全文
05
2019/08

成都石室划水游记

Day 0

早上起得很早精力不好。

到了火车站,排队的时候在队伍中换个位置,后面的一堆中年女士一下子就沸腾了到处喷我插队什么之内的不要脸没教养有神经病没有公德心还是不是人啊有毒吧快走啊插什么队啊凭什么插队啊快一边去,这种人渣被插队活该,何况只是在这群神经前面换个位置而已,有没有影响到什么,有病。

突然发现不是去 $cdqz$ 而是去石室 $\rm{QAQ}$ 。

做了火车又做地铁然后走路,下午五点多才到学校,校门酷似庙门,差点让人以为走错了

宿舍里面没有空调,连个插座貌似是装饰插座。接着寝室老师将我们叫去,给我们灌输纪律以及生活方面的问题,然后说道了洗衣服,寝室老师来了一句:"衣服可以自己洗,到时候爬到五楼去找没人要的衣架洗洗将就晾着就好。当然,也可以让我们洗,用学校的洗衣机,一件衣物两块钱,超实惠的~"

整理了一下去吃完饭,发现这一块好像是老城区,连个超市都没有...

有点尴尬。

Day 1

清北的讲师咕咕咕咕了...

于是在机房里面自习。

不得不喷一下这里的电脑,很卡,然后就是自带毒霸卡,所以你装一个 $\rm{TIM}$ 就给你蓝屏了然后给你重启清空你的资料后让你继续用~

一上午蓝了四次......导致没做些什么。

突然一下就下起大雨了,很像 $2017$ 年暑假那次将我们那一带几个小区全部淹了的大雨。中午吃饭,雨伞坏了只能手动撑,于是想也不想直接手撑然后一头扎进雨中,最后的代价就是裤子可以拧出一地水$+$鞋子重量$\times2$ ,回寝室后整理鞋子发现水完全浸进鞋子了,估计鞋子废了嘤嘤嘤。

下午安排了三道题,貌似没睡好,于是基本上全程打摆。其实第一题很好拿部分分,暴力 $\rm{DP}$ 就有 $70$ 了。然后第二题是一个很蠢的 $\rm{LCT}$ ,基本上是全场切的那种。第三题应该是容斥+$\rm{DP}$ ,然是也只会部分分做法。

最后没有打一道题,不想打,想睡觉。

再吐槽一句:这里的键盘好shi啊

Day 2

早饭居然升级了一个档次[震惊.jpg]。

上午清华的学长终于来讲课了,只不过说好的"数据结构难题选讲"为什么变成了"多项式全家桶+生成函数"?先讲 $\rm{FFT}$ ,超级详细的那种。

讲了大概五分钟后石室的总教练上去了:"这个他们都会了"。
哈。

然后就开始讲生成函数,几乎是一路飙车,一张 $\rm{PPT}$ 的笔记要一分钟才能做完,但是他 $5$ 秒就跳了,到头来我这种写字很慢的菜狗自然是没记什么。

牛顿迭代也讲了,只不过很迷,而且在其中的多项式全家桶什么的都是直接微积分,让我们背公式,这可真还行,准备记录的时候又跳了。

上午讲完课后将 $\rm{PPT}$ 发了下来,好评。

午饭好评。

下午从 $\rm{FWT}$ 讲到 $\rm{CH}$(窝也不知道是什么于是就这样简称了) 再讲到 $\rm{BM}$ ,反正 $\rm{FWT}$ 不会证明,后面的内容也是全程掉线,干脆去康康上午的算了,反正下午没有控制电脑。

晚饭好评。

晚上复习 $\rm{NTT}$ ,然后复习多项式求逆,接着过了多项式对数函数的板子,然后水知乎,旁边的 $\rm{RicardoShips}$ 一直在和 $\rm{Decoration}$ 商量面基的事情,$\rm{CYJian}$ 居然也想去,说是要 $\rm{RicardoShips}$ 帮忙付钱,$\rm{RicardoShips}$ 居然同意了,默哀 $\rm{RicardoShips}$ 的钱包一秒。

会了多项式指数函数,但是没时间打了于是就没打了


多项式对数函数:

给定 $\rm{F(x)}$ ,求一个多项式 $\rm{G(x)}$ ,使得:

$$ \rm{G(x)\equiv \ln\ F(x)} $$

答案对 $998244353$ 取模。

考虑对两边同时求导,最后式子会变成这样:

$$ \rm{G(x)=\frac{F'(x)}{F(x)}} $$

上面的 $\rm{F'(x)}$ 是 $\rm{F(x)}$ 的导数,用多项式求导可得。然后多项式求逆解决 $\rm{\frac{F'(x)}{F(x)}}$ ,最后用多项式积分求出 $\rm{G(x)}$ .

求导公式

$$ x^{a'}=ax^{a-1} $$

积分公式

$$ \int x^adx=\frac{1}{a+1}x^{a+1} $$


Day 3

早饭好评。

上午讲题,主题大概是单位根反演/循环卷积/集合幂卷积之内的题目,从第一题开始就掉线了。


T1:「$\rm{THUPC2017}$」小 $\rm{L}$ 的计算题 / $\rm{Sum}$

这题可以用牛顿多项式做,不过也可以用生成函数搞。

设 $f_i$ 的 $\rm{OGF}$ 为 $\rm{F(x)}$,那么有:

$$ \begin{aligned} F(x)&=\sum_{i=0}^{\infty} f_ix^i\\ &=\sum_{i=0}^{\infty} \sum_{k=1}^{n}a_k^ix^i\\ &=\sum_{k=1}^{n}\frac{1}{1-a_kx}\\ &=\sum_{k=1}^{n}1+\frac{a_kx}{1-a_kx}\\ &=n+x\sum_{k=1}^{n}\frac{a_k}{1-a_kx}\\ &=n-x\sum_{k=1}^{n}\frac{-a_k}{1-a_kx}\\ \end{aligned} $$

众所周知:

$$ \ln(x)'=\frac{1}{x}\\ \ln(1+x\times y)'=\frac{x}{1+x\times y}\\ \ln(x\times y)=\ln(x)+\ln(y) $$

那么上面的就很显然了:

$$ \begin{aligned} F(x)&=n-x\sum_{k=1}^{n}\ln'(1-a_kx)\\ F(x)&=n-x\times \ln(\prod_{k=1}^{n}(1-a_kx))'\\ \end{aligned} $$

分治 $\rm{FFT} $ $+$ 多项式对数函数 $+$ 多项式求导即可。


上午我就只听懂这题。

午饭好评

下午掉线了,逐渐开始研究如何摆脱电脑控制

晚饭差评

晚自习水知乎+写日记 $\rm{QAQ}$ ,有点不想打上午的题了。

还是打一下吧。

晚上 $\rm{RicardoShips}$ 主动和 $\rm{Decoration}$ 商量爆照的事,然后 $\rm{RicardoShips}$ 特别想看到 $\rm{Deco}$ 的真人照,于是先将 $\rm{CYJian}$ 的大头滑稽照爆出来了,并且让 $\rm{Deco}$ 爆半边照,$\rm{Deco}$ 就要动心了。

然后 $\rm{CYJian}$ 来了,发现我们不对劲,赶快来抢键盘,由于 $\rm{CYJian}$ 过于强猛,看到了不该看到的东西...

咳咳,于是 $\rm{Deco}$ 真的爆了半边照(其实是下半身...),求 $\rm{CYJian}$ 的心理阴影面积...

Day 4

咕掉了,补一下吧 $\rm{QAQ}$ 。

上午讲的斯特林,简单的讲了一下两类斯特林数的求法,然后就开始讲例题了。幸好学过斯特林一下就跟上了,例题都听懂了,就是最后两题斯特林反演完全掉线了。

午饭好评

下午开始数据结构 ... $\rm{PPT}$ 因该是赶工的有很多纰漏。

晚上不记得干了什么...


Day 5

上午不是 $\rm{dzy}$ 讲课了,直接讲的莫比乌斯反演。题目不算恶心,至少 $\rm{JerryC}$ 都切掉了。

下午讲一系列筛法,讲了一堆我会的,不讲洲阁筛差评(貌似洲阁筛也没什么用?),因为都会了所以干其他的事去了...

晚上学习+知乎


Day 6

讲什么数学常识,掉线了...


Day 7

上午考试,发现在考场上自己啥都不会,最后 $60$ 分苟在了 $rk 11$。

下午划水改题。

晚上居然放假了,于是几个人下午下了课就出去吃火锅了...

本来八点有一场 $\rm{CF}$ 的,却由于种种奇奇怪怪的原因没去成机房,没打成。后来看题,发现很蠢,$\rm{CYJian}$ 将所有的题全切了,$orz$ 。

$\rm{CYJian}$ :这种傻逼场随随便便 $\rm{AK}$ ,于是我就可以直接上橙了。


Day 8

讲什么"数据结构经典题",一上来就是 $\rm{Ynoi}$ 。

发现还是有些简单题的,晚上敲。

结果一敲就是一堆,树剖$+ vector$ 还没过得去,只有 $80$ ,最后几个点全部 $\rm{T}$ 了,发现 $vector$ 要换成 $Splay$ ,还要无限卡常,不然过不了,不知道树剖要不要换成 $\rm{LCT}$ ,好像树剖的复杂度是 $O(n\log^2 n)$ 的,会被卡掉。

这样代码估计就有 $270^+$ 了,果然 $\rm{Ynoi}$ 不是什么好惹的东西。

怎么越更越少了(雾


咕咕咕咕咕咕咕咕咕咕咕

最后修改:2019 年 08 月 22 日 03 : 48 PM

1 条评论

  1. Anonymous

    gugugu

发表评论