whj什么都不会系列-1 Posted on 2018-12-14 | Edited on 2019-09-09 | Comments: 退役了只有一直没怎么做题,感觉水平退步了不少,以前一些比较显然的思路现在可能都想不到了. 这样下去肯定是不行的,我尽量时不时做点水题写点题解恢复一点智商吧. 题意给定$n,m$,求有多少对$(i,j)$满足$1\le i\le n,1\le j\le m$且$\gcd(i,j)$为素数. 共$T$组数据. $n\le 10^7,T\le 10^4$ Read more »
O(1)快速乘 Posted on 2018-11-30 | Edited on 2019-09-09 | Comments: AFO有段时间了,感觉自己什么都不会了,随便研究点东西证明我还活着…… Read more »
黑科技 Posted on 2018-09-30 | Edited on 2019-09-09 | Comments: 好久没写博客了,随便扔点东西上来除个草. 其实也说不上是黑科技,就是自己平时折腾linux,折腾vim之类的东西的时候发现的一些小技巧罢了. Read more »
NOI2018退役记 Posted on 2018-09-01 | Edited on 2019-09-09 | Comments: Your browser does not support the audio element. 退役之后一直有点消沉,没有写退役记什么的,最近想了想还是多少放点东西上来. Read more »
uoj50题解 Posted on 2018-08-17 | Edited on 2019-09-09 | Comments: 分治fft是非常明显的做法,不过这样是$\mathcal O(n\log^2n)$的. 把生成函数弄出来之后会发现它是个微分方程,可以有一些神奇的方法来解,具体可以看UR3的题解. Read more »
loj2541题解 Posted on 2018-07-16 | Edited on 2019-09-09 | Comments: 这种求某个东西在最后一个的概率之类的其实可以考虑容斥,设钦定一个集合$S$在它后面的概率为$f(S)$,那么最后的答案为$\sum (-1)^{|S|}f(S)$. Read more »
uoj387题解 Posted on 2018-07-15 | Edited on 2019-09-09 | Comments: 学到了一个新的技巧,树形的依赖关系,把顺序翻转,就可以在依赖父亲和依赖子树之间相互转化. Read more »
bzoj2324题解 Posted on 2018-07-07 | Edited on 2019-09-09 | Comments: 前置技能:DAG的最小路径覆盖和最小链覆盖. Read more »