• 等级
  • 22566 访问
  • 256 原创
  • 0 转发
  • 22321 排名
  • 7 评论
  • 19 获赞

学习笔记第四十三节:Min_25筛

正题听说这个东西是最近几年,某个大佬Min_25提出的,帮助我们解决了许多积性函数前缀和问题。为了方便,我们以loj6053:简单的函数一题来讲一讲什么是Min_25筛。首先,正如开头所提到的,Min_25筛是用来解决积性函数前缀和问题的。而且,根据我的了解,这个积性函数要满足下面几个性质:1.对于一个质数,一定要是关于p的一个多项式;2.对于一个质...

2019-04-24 19:33:01

苏州集训营总结

正题毋庸置疑的,在这次集训营中必定学到了很多新东西,在这里不一一总结,主要说一下这次集训营给我的感受与下一步的规划。首先,这次集训的大佬比上次多了许多,比如说常州中学的三位神仙们,还有zhf大佬。(我太菜了flag1所以这样一来,课就上的很懵逼,有些地方大佬懂了,觉得挺显然的。而我还要思考半天,举一些例子才能证明一些东西的正确性。(我太菜了fla...

2019-03-30 04:17:27

学习笔记第四十二节:斯特林数的性质,反演以及二项式反演

正题在这里就不多说,直接说几条式子。先陈述几个事实:接着我们可以发现一些东西。根据第二类斯特林数的通项公式,我们可以知道:然后可以化成卷积的形式:然后就可以nlogn求出第n行的斯特林数了!接着是一个非常显然的公式:,(枚举箱子,然后将n个球放进m个箱子里面...

2019-03-27 20:40:31

学习笔记第四十一节:Min-Max反演

正题我们探究着反演的奥妙,突然发现有一条式子,很奇怪:接着,有一群人就把它们推广成普遍的式子:我们就可以做很多事情了:比如说遇到一些max值很难求出来的,而且min值很容易得到的,我们可以通过Min-Max反演来枚举子集使得其算出max值。就像这一题:[HAOI2015...

2019-03-27 20:03:21

苏州省选冲刺第二天

正题现在每天都是三步走吧,早上考5个小时,午饭,下午讲题加补题,晚饭,讲专题。这两天讲了一些奇技淫巧(数论和多项式,而且是很冷门那种。早上考了三道题,其中有两道题不错(第3题莫比乌斯反演加四元环计数我也不会,分享一下:第一题:已知,n个变量,m个方程组为这样的形式,每次合并指定的方程组,形成新的方程组,共m-1次,每次...

2019-03-20 00:06:48

玩游戏,洛谷P4705,NTT+生成函数+可怕的公式推导+可怕的代码

正题     这个游戏整整玩了我三天。     题意就是要你求。还要你求。那我们暂且先不理会nm这玩意儿。     利用二项式定理,化简一下可以得到:          看到了喜闻乐见的卷积形式,但是我们难以求出可用于卷积的两个数组。     这个其实可以用生成函数来解决,在我的博客中就以这个模型来介绍生成函数,大家可以看看。     所以我们最后再用这两...

2019-01-24 16:20:49

学习笔记第四十节:生成函数与求导、积分、对数

正题     对于一串数字,我们可以把它写成一条函数,以便于化简和计算。     比如说,那么这个数列的生成函数就是,而其中的x是没有意义的,真正有意义的只有系数,所以我们在化简式子时,x可以取任意实数。     用生成函数以及一些关于对数、求导之类的数学方法,我们可以把问题简化。     比如说,我们要求。     如果暴力枚举,我们就需要的时间,但是,我们看看生成...

2019-01-24 16:06:11

Hard Nim,bzoj4589,快速幂+FWT

正题   给出n和m,要求选出n个在中的质数,使得其异或和为0的方案数。   首先我们先处理出来1到m的质数,并建立一个类似于bool数组来记录i是否为质数。   接着,让这个长得像bool数组的数组求n次沃尔什变换,输出数组的第0位就可以了。   因为数位就相当于他的值,而数位上的数相当于方案数,做一次沃尔什变换相当于加多一个数。   我们看到n...

2019-01-22 15:30:12

学习笔记第三十九节:快速沃尔什变换(FWT)

正题我们学会了快速傅立叶变换,狄利克雷卷积,现在我们来解决一下快速沃尔什变换。它主要是解决这样的问题的:。也就是说其中那个你看不懂的符号指的是三则运算的其中一种:or,and,xor。怎么做?我们来模仿一下解决多项式乘法的过程,我们先是把原数组做一次傅立叶变换,然后再相乘,最后再做一次逆变换。...

2019-01-22 15:18:56

[JSOI2012]分零食,洛谷P5075,有趣的公式推导和多项式求逆

正题   题目链接点这里   考虑一个m次多项式,。   当只有一个人的时候,贡献恰好是   当有两个人的时候,贡献恰好是。   因为第m项是由转移过来的,因为我们已经规定了。   所以恰好是两个人的贡献,以此类推。   答案就等于。   发现是等比数列求和,在前面补上一个1,就等于。   小括号指的是一个多...

2019-01-12 08:15:29

学习笔记第三十八节:NTT,MTT,多项式求逆

正题NTT假设给出两个多项式,求他们的傅里叶卷积是及其简单的。但是如果这两个多项式的值域为P,那么在运算的过程中,某一位的最大值是,因为FFT本身自带一个limit。所以当的时候,,很明显会爆longdouble.通常这类问题他还会教你mod一个质数。怎么做?首先考虑FFT中的替换成q,可以使...

2019-01-12 08:00:33

[HEOI2016/TJOI2016]求和,洛谷P4091,第二类斯特林数与FFT

正题   这题的目的很明了:   求。   首先我们要知道,关于证明可以参考我的博客。   然后换进去:       交换枚举顺序:       然后就可以发现后面的东西可以直接设为,而设。   那么。   预处理G函数,和H函数,H函数的上面相当于一个等比数列求和,当时,等于0.时,等于。否则等于。...

2019-01-08 12:54:16

[TJOI2017]DNA,洛谷P3763,暗藏玄机的字符串FFT

正题   这题正解SAM?蒟蒻表示不懂。   拿起了FFT乱搞。   首先,题目没有说字符集只有{A,T,C,G};四种。   然后,我们就可以考虑FFT。   用表示偏转i位之后,文本串和模式串的差异。   那么就有   然后很明显,我们可以先令,。   就可以写成。   是不是很像卷积?   这...

2019-01-03 17:15:34

[ZJOI2014]力,洛谷P3338,FFT

正题   这题是我做过的最正经的FFT了。   其实   出题人很良心,已经帮你把它拆开了。   我们设   那么   前面的很明显是一个多项式乘法把,后面令,那么令,然后多项式乘法就可以了。    这些限制可以丢掉,因为不满足的时候没有值,特殊的,我们只需要令就可以了。#include<cmath>#incl...

2019-01-03 16:59:39

[AHOI2001]多项式乘法,洛谷P2553,字符串+FFT?

正题    这题就是烦吧。    关键是字符串的处理,然后两个做一次多项式乘法就输出?#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>usingnamespacestd;stru...

2019-01-03 16:52:08

学习笔记第三十七节:多项式与FFT

正题   解决问题:for(inti=0;i<n;i++)for(intj=0;j<n;j++)h[i+j]+=f[i]*g[j];  前置知识    定义,其中i为负数单位。    在这里我们假设z是一个复数,也就是说    ,Re为实部,Lm为虚部。    加减法就是对应相加减:也就是说    但是乘法...

2019-01-03 14:02:47

草稿

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;intn,T,R,m;structnode{ intp,s,t,id; booloperator...

2018-12-22 12:06:35

[SDOI2018]旧试题,洛谷P4619,莫比乌斯反演+三元环计数

正题   突然发现很多SDOI的题   题目也很直白,要求:。   后面的。   证明可以仿照约数个数和一题。   然后换进去,就变成   变形一下:。   发现后面是很有规律的,其实就是的约数个数和。   公式就变成了。   发现,当时,这条式子没有贡献。   那么考虑互不相等的。若,那么就从连一条权值为的边。...

2018-12-22 09:36:41

[SDOI2017]数字表格,洛谷P3704,莫比乌斯反演+狄利克雷卷积

正题   题目链接   求  。   换一个计算方法,枚举gcd,答案就是。   其中就是的个数。   那么       换进去,答案就是   枚举T,就变成   显然可以把提出来。   就变成   括号里面的设为F,。   很明显是一个另类的狄利克雷卷积的形式。   ...

2018-12-22 08:06:40

[SDOI2015]约数个数和,洛谷P3327,莫比乌斯反演+约数定理?

正题   题目链接点这里   题目了然:       但我们知道   为什么呢?   我们直到假如   那么约数个数和就是   考虑产生贡献的x,y是什么样子的:要不x不含a质因子,y含质因子;要不x含a质因子,y不含,要么两个都不含。   假设i里面是a质因子的指数为,j里面a质因子的指数为,那么a质因子产生...

2018-12-22 07:49:29

Deep_Kevin

关注
  • 学生
  • 中国 广东省 中山市
奖章
  • 持之以恒