FFT

适合NTT的模数

本来用std::set存被线性筛筛掉的数,结果跑到1m左右内存就炸了,电脑完全卡死。记录质数倒不怎么担心,要筛出后面的质数需要的质数数量是比较少的。 于是我改成bitset+vector+-O2,秒出答案。 我可能会用998244353998244353998244353(UOJ模数),924844033924844033924844033(AtCoder模数)以及226∗7+12^{26}* 7+12​26​​∗7+1。这几个比较好记,而且已经够处理P≤109P\leq10^9P≤10​9​​以及n≤106n\leq10^

NOIP2017小结

NOIP过去快一周了,心情逐渐平静,头脑逐渐清醒,是时候写写总结了。 以年份命名的事物,每次都能让你感觉到新颖,但又每每让你感到时光的流逝。每年的NOIP都激动人心,年复一年,又隐隐显得平淡。 OI生涯中,我最畏惧,也最难以忘却的,就是NOIP2016 Day1和NOI2017 Day2最后十分钟那种绝望的心情。这么多场比赛下来,我发现“OI式绝望”可以大概分类如下: NOIP2016 Day1、APIO2017、NOI2017 Day2:不会写正解,会写暴力,但是前面的时间全部拿来想正解,剩下时间不够写暴力,只能干着急,直到最后一分钟还在闷头想正解,等待奇迹出现; GDOI2017

信号与系统

复变函数与拉普拉斯变换

今天才发现,傅立叶变换原来是拉普拉斯变换的特殊形式。那就学习一下复变函数和拉普拉斯变换吧。 一个复变函数是自变量和因变量都是复数的函数,平常的单变量函数是一种特殊形式。 基本的那些多项式应该没有什么问题,学过虚数就会算了。比较麻烦的是超越函数。让我们用熟悉的实数来推,设z=a+bi,a,b∈Rz=a+bi,a,b\in Rz=a+bi,a,b∈R,由欧拉公式有: ez=ea+bi=ea⋅ebi=ea(

二分图

二分图进阶

在二分图的各种证明中,递归增广的证明思想非常普遍。 最大匹配 边匹配是一个没有共用顶点的边的集合。 Hall定理:二分图的左侧的点能够全部匹配上的充要条件是,对于左侧的点的任意一个子集SSS,都至少直接连上了∣S∣\left|S\right|∣S∣个右边的点(Marriage Condition)。 证明: 必要性显然。 充分性的证明过程,就是匈牙利算法寻找增广路的过程。不失一般性地,设左边点数小于等于右边点数且左边的点满足MC。考虑左边一个没有被匹配上的点,根据Hall定理,它至少连到了右边的一个点。如果这个点没有匹配上,那就可以匹配上;否则把右边这个点的匹配点加入左边的集合,由MC知至少连到了右边的两个点,任选一个新点,再类似讨论。一旦发现一个没有匹配上的右边的点,就可以沿着增广路增广。

Treap

一个关于Treap优化的点子

我今天做了一道可持久化Treap的题目。因为我不会写非旋转版Treap,更不会写可持久化非旋转版Treap,所以就想着法子绕开这个禁区。当然,我这么做是不对的,认真学习的我应该正面对抗来自Treap的代码量攻击;但是我在这偷懒的过程中却想出了一种不基于随机性、代码量小的做法。这种做法我感觉应该可以拓展,但是暂时还没想到怎么应用于更多的问题。 题目大意 交互题。 在题目给的头文件里,定义了一种结构体Data、满足交换律和结合律的函数Data F(Data x,Data y)、还有一个一开始为空的序列。我们需要实现对该序列的三种操作: 往第ididid个序列后面加入一个DataDataData,作为一个新序列; 从第ididid个序列最后面删去一个元素,作为一个新序列; 问第ididid个序列[l,r][l,r][l,

数论

洲阁筛

用上线性筛,我们可以用O(n)O(n)O(n)的线性时间求一个积性函数的点值;如果一个函数和另一个容易求前缀和的函数的狄利克雷卷积的前缀和也很好求,用上杜教筛,我们可以在O(n23)O(n^\frac{2}{3})O(n​​3​​2​​​​)的时间里求这个函数的前缀和。但是在积性这样一个限制下,仍有十分广阔的空间我们没有做研究。洲阁筛就是一个能在O(n34logn)O(\frac{n^\frac{3}{4}}{\log

支配树

支配树速成记录

支配树和其他图论知识没什么关系,学习曲线极大,我在省选前根本静不下心来好好看;现在也没这个耐心,只是简单地看了看概念,从结论自己脑补出证明,参考了几篇博客,止步于此。当然,没有理解透的东西一定是记不牢的,所以为了在以后复习的时候能够快速地恢复对支配树的记忆,我把现在能理解的东西先记录下来吧。 想了解严格的证明和更多拓展知识,请见L-T原论文。本着“速成”的目的,我没有仔细研究这篇论文,所以在下面没有作严格的证明,也不保证正确性,大家就看着玩玩吧。如果你想把我批判一番,欢迎联系。 正文开始。 支配点 俗话说,条条大路通罗马(Rome)。在一个单源(源点设为rrr)有向图中,如果删掉点uuu后,从罗马出发就到不了vvv了,

信号与系统

快速傅立叶变换

快速傅立叶变换其实不难,编码也不复杂;但是一开始接触的太高深,在阅读过大量有关但无用的资料之后,终于总结了一点自己的心得体会,记于此。 既然BZOJ 2017省选模拟赛Day1 T3用了FFT,那我就来谈一谈FFT吧。 去年寒假在《算法导论》上看到了快速傅立叶变换,没有认真学;去年暑假上了快速傅立叶变换的课,没有实现过;直到今天,我才真正意识到我也能写的出来! 想求两个n−1n-1n−1次多项式(选n−1n-1n−1次是因为这样总共有nnn个系数,比较方便编程计算)的乘积,我们一般是O(n2)O(n^2)O(n​

BZOJ

BZOJ 省队十连测第一场

Claris出题。BZOJ Begin 3738,3739,3740。 试题难度一高,我这样的蒟蒻当然是一道题都做不出来的。考试5个小时前3个小时水掉了,最后两个小时半个小时拿去吃饭,一个半小时打暴力,混了个60分。 shopping 0 highway 30 sailing 30 T1输入输出文件名写成了“highway"……下次模拟赛的时候要注意了。 shopping 考虑没有消费限制的话,直接插板就好了。允许为空,所以共n+kn+kn+k个球n+k−1n+k-1n+

BZOJ

BZOJ2017省选推广赛

因为是推广赛,所以这三道题在比完赛之后是公开的:BZOJ4765、BZOJ4766、BZOJ4767。 普通计算姬 看到求子树和,很容易想到ETT。但是ETT的编码不太方便,看有没有可以优化的地方。于是发现树的形态不会变,那么只要用DFS序再用一个区间数据结构维护一下就好了。 省选题目会这么简单吗?当然不会啦。要求子树和之后还要求区间子树和,这个就比较麻烦了。思索了许久之后,想起之前对付这种修改一个数据要更新两段区间和的题目的时候,主要的解决办法是分块。 那么把[1,n][1,n][1,n]按n\sqrt{n}√​n​​​分块记录子树和的区间和,然后对每个节点用O(n)

数论

莫比乌斯反演

前言 这篇文章会很长!我会先从容斥原理开始讲,然后是线性筛,积性函数,欧拉函数,莫比乌斯反演,莫比乌斯函数,以及一些习题。这个问题很早就在《组合数学》上看到过,但是完全看不懂。GDOI2016的时候感觉基本上所有其他选手都会,讲得神乎其神,意识到自己与他人的差距,而且这个差距必须补上来。这几天我花了大量的时间,参考网上的资料以及教材,归纳出了一个自己比较容易理解的方法,做了一个总结。希望在写完这篇总结之后,能够在数论方面有更深刻的理解。 容斥原理 小学奥数题 先用一个小学奥数的问题来引入: 有一根30cm长的木棍,从头开始,先每隔2cm切一刀,再每隔3cm切一刀,再每隔5cm切一刀,问最终剩下多少段木棍? 如果只考虑每隔2cm切一刀,

GDKOI

GDKOI2017

赛前准备 GDOI和GDKOI的组委会都是广东省里面的,我猜测GDKOI会对GDOI有一定的导向作用。所以准备好GDKOI还是蛮重要的。 稍微翻看一下前几年的题目,总结起来,有一些考点是每年必考的,比如说线段树(魔卡少女、看门狗)、网络流(这个很正常)。去年的题目考了好几道模板,没能早些学习信竞,可以说是一大遗憾。 在准备的时候的另一收获是《算法竞赛入门经典》和它的《训练指南》,这两本书对算法竞赛的总结真的是非常全面的,可以让初学者少走不少弯路。我入门用的是《信息学竞赛一本通》,宋新波老师主编的,感觉没有那么权威,很多NOIP考的内容也没有提到,更别说省选了。 每次比赛前总会认识到自己的不足:还有多少题目没做,还有多少知识点没学,还有多少算法没练习模板;赛后,实力一时提升,

POJ

POJ1077 Eight

这道题是去年暑假就开始做的题,但是去年结构体实现的优先队列没写好,所以一直没AC。半年时光,我的代码风格也从结构体+指针逐步转变为数组模拟,只为提高那一点点效率。这样在使用Dev C++调试的时候也会更方便一些。 搜索 这道题使用启发式的A*搜索。A*的本质是广搜,但是对于只需要出一个可行解的问题会比广搜快。 在广搜的时候,将队列改为优先队列,优先采用最靠近答案的状态来拓展。计算是否更优一般取两部分函数的,一部分是记录已经走的步数,另一部分是估计还要走的步数。这也就是A*算法算启发式算法的地方,因为估计函数一般没有办法获得准确值,估计的很小不代表实际很小。 对于这道题来说,我认为不必要记录已经走的步数。因为我们只需要尽可能快的出答案,不需要答案最短。我使用了int est[]数组来储存估计还需要的步数,

博弈

数独程序开发文档

版权声明:本文及数独程序基于MIT协议发布。 背景 这半个学期的末尾,我们数学课一直在学习算法、程序框图以及初步的程序。寒假作业里面提供了二选一的作业: 完成一个统计实习报告 自学一门计算机程序设计语言,并开发一个小型的软件 我当然选择了第二个。 我本来想写一个KMP,或者后缀树,这样才能体现算法的精髓(至少我是这么认为的)。但是没有测试数据量的话这个高效算法的强大又体现不出来。我只得做了一个比较实用的小程序:数独计算器。 源码 #include <iostream> #include <cstdio> #include <cstring> using namespace

SMOJ

2016.10.7 NOIP模拟赛

SMOJ/1433 立方体 直接模拟就好,开一个分数类型的结构体,记得要用long long,不需要高精度。一开始调试的时候发现数据一超过2147483648就会出问题,开了unsigned long long还是这样。仔细检查之后发现有一个地方的int没有改成long long,浪费了半个小时,实在不应该。 SMOJ/1343 字符串的划分 这题错的比较惨烈,没有拿到分。我分享一下我的做法吧。 首先从头开始贪心,碰到出现过的字母就截断,重置exist数组。这样估计是能得到最小段数的。为了得到最小字典序,我又从后往前扫一遍,如果在前一截中出现了一个比当前截开头更小的字母,那就把当前截的开头移过去。可以证明这样做能够使程序算出来的答案更靠近正确答案,但是没有办法证明这样做就能得到正确答案! SMOJ/

最短路

2016.10.6 NOIP模拟赛总结

SMOJ/1426 最小生成树 我一开始是直接把所有的点两两连边,即N2N^2N​2​​条边,使用kruskal解决,时间复杂度O(n2∗log2n)O(n^2*\log^2n)O(n​2​​∗log​2​​n),自然超时,过了一半的点。 对于边数过多的最小生成树,一般的策略就是删边。其实之前刘励行给我看的一道题就用了类似的思路,但是今天没想起来。 我们可以先转化一下问题:由于每两个点之间的距离为Disi,j=min(