dzy love xx系列

最近脑洞大开……看到dzy love xx系列就想到这个:

dzy:诸君,我喜欢……
朱军:你tm什么都喜欢!

以上都是脑洞……就当没看见好了。

实际上我也懒得写那些随处都找得到题解的题目的题解。
dzy love math系列的第一题我当时就用弃疗法过的,就不说了。而且目测也很容易就能找到题解的样子。
dzy love math2当时我在xjoi看到这题就吓尿了,不过后来想了一想发现和cc的change差不多,我毕竟也是嘴巴上a掉change的人(喂)就不扯了(喂),
change那题的题解传送门:
http://discuss.codechef.com/questions/7416/change-editorial
以及http://xudyh.github.io/solution/2014/03/22/codechef-change/
以及http://pan.baidu.com/s/1bn1TviR
dzy love math3——我现在上不去bzoj,也不记得题面……以后补吧。
dzy love math4——传送门:http://duxyz.github.io/solution/2014/04/03/DZY-Loves-Math-4/
dzy love math5——传送门: http://foreseeable97.logdown.com/posts/198345-dzy-love-xx-series

其实这题在3月26日——省选前夕策爷就给我出过,当时n=1000……当然因为当时是要省选了,我在浪,没时间管这题。
最近好好看了一下这题,发现推导还是好推的。

不妨假设(质数分解

其实我们的求和式子就是:

交换求和顺序:

目标转移为快速求

然后我们考虑对这个求和式的贡献,我们会发现它在求和式中出现的次数即

的正整数解的个数(其中)

我们不妨定义表示在第i个求和式中出现的次数。

那么就有等式

很容易就会发现是能通过dp求出来的。。

不过不够快,需要更好的做法。

考虑从生成函数的角度来看

很容易发现

实际上是多项式

次项系数。

转化一下这个多项式。

但是转化之后还是不能帮助我们来快速求的值。。

但这已经有很大帮助了。

我们来注意一下是质数时候的取值。

很容易发现

那么

刚才我们已经说了是某个多项式的系数。

那么就可以看作时候的值减去0次项的值(就是1)

所以

至此问题大致解决。。。

dzy love math6
xyz出的题面,我怎么可能会做
(推导待补中

dzy love math7
卧槽为啥不出个bzoj 3000题合1,3合1有意思?
(根本不会做

dzy love chinese系列
不知道是谁出的题目,
反正两道傻逼题……
具体参考ydc的题解吧。http://ydcydcy1.blog.163.com/blog/static/21608904020144891248544/
当然第二道那道随机化乱搞的可以看一下杜教的介绍:唉杜教的钓鱼文不见了?

dzy love chemistry
我不会写随处找得到题解的题目的题解的。
传送门:http://jiruyi910387714.is-programmer.com/posts/44736.html
dzy love physics
bzoj挂了看不了题。映像中是道力学题……(你好歹出道光学电学的啊,经典力学有毛好玩的

顺便我坚信出chinese、chemistry以及physics几道题的人急需接受治疗。

Comments

comments powered by Disqus