雕像爆炸的充要条件是“唔噗噗噗”。
这时候我们就称 “雕像爆炸” 可以推出 “唔噗噗噗”,同时 “唔噗噗噗” 也可以推出 “雕像爆炸”。这记作:
和符号
从左到右
给定一个周长为
的圆,从一个点出发,有 个黑白熊雕像,编号为 到 ,第 个雕像在顺
时针米处,如果你没有在 秒内收集到这个黑白熊雕像,那么这个雕像就会发出“唔噗噗噗”
的声音然后爆炸。
想读懂这句话是什么意思,关键在于要读懂这句话。
首先我们来看第一句,“给定一个周长为
同时,我们可以在下面的一句话中找到一些特殊而奇妙、神奇又美好、可爱又萌萌的性质:
第一行两个整数
代表雕像数和圆的周长。
太对了!这说明
同时,我们还注意到
这句话的另一个表达方式是:
还有一个表达方式:
中间那些部分没啥用,我们就先跳过了。
广告之后马上回来!
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
你好,我是广告。
我们接着品析上面的这段话。
大家看,“你好”这个词象征着欢迎,而广告这个词则是表达了——
对不起看错行了
关键的部分来了!
如果你没有在
秒内收集到这个黑白熊雕像,那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。
啊,我们看到我们想要的东西了。
“唔噗噗噗”是一个地地道道的拟声词,它的发音为:
“黑白熊”也是一个关键,需要理解。想到黑白熊,我们立刻想起来一个非常有名以至于妇孺皆知的动物:熊猫。这就不难发现为什么要建造“黑白熊雕像”了!敬仰熊猫,为它立雕像,这不是人间大义、值得歌颂千古的伟大善事!来,我们肃立一分钟,为我们可爱的大熊猫敬礼!
诶,那雕像为什么会爆炸呢?
毁坏文物雕像,会遭到判刑;毁坏大熊猫雕像,却是不尊重国家的行为。再结合一个我们忽略的重要信息:
现在 JOI 君在这个点……
JOI,即日本国赛。
小日子的阴谋浮上了水面!
结合“唔噗噗噗”这个非常难崩又难以理解的词语,不难想到小日子们想用这样可爱的外表来进行一系列阴谋活动。这正是他们能干出来的事!
这样我们就得到了结论:可爱的黑白熊猫雕像爆炸是一场早有预谋的攻击,其主谋为小日子国度,妄图使用最新研发的代号
这样我们证明了一件事:“唔噗噗噗”是可以推出雕像爆炸的,即
从右到左
雕像爆炸怎么能推出“唔噗噗噗”呢?
我们利用反证法。
首先我们证明一个引理:计算等差数列的和的算法太快了,不够慢。
大家知道计算等差数列的和的公式吗?我们记项数为
为了看出我们是怎么劣化这个算法的,不妨设
我们来推一个式子:
我们可以预处理出
能不能再慢点呢?可以!
我们预处理出
这样的时间复杂度是什么呢?一个 naive 的上界显然是
我们可以认为,整个计算过程分为
,此时数论分块的块长为 ,每次调用杜教筛的时间复杂度为 (预处理值域内),这一部分的时间复杂度为 。 ,此时数论分块的块长不再是 ,但是杜教筛的时间复杂度仍然是 ,杜教筛调用的次数是 的,因此这部分的时间复杂度是 。 ,这部分杜教筛的耗时不再是 而是 ,而块数为 ,因此此时间复杂度为 。
综上,我们得到了这个算法的时间复杂度是线性时间查询、
回过头来,我们证明这个引理有什么用呢?
我们仔细审视“唔噗噗噗”一词。第一个字“唔”可以被看做一个等差数列的首项,而后面的“噗”象征着对每一项增加
我们捡雕像,可以看做对这个数列求和,而经过上面的讨论,我们需要的时间是
这样我们证明了一件事:“雕像爆炸”是可以推出唔噗噗噗的,即
我们回顾一下我们的探索过程。
证明部分生动具体地应用了“若
在证明过程中,我们还介绍了一种由 @秦屎皇 口胡的
好了,今天的分享就到这里,我是 @秦屎皇。