看心情填坑

有必要说的没必要说的都在这里了。

主要是一些(貌似)我比较专长别人研究的比较少的东西。

其他OJ上或多或少都有官方题解就不多说了，都是51nod一些过的人比较少的题。

1233

经过几波差分之后可以变成数论函数卷组合数的形式，具体都在讨论里。

这个题思想就在于杜教筛其实是不要求两个函数是积性函数，只要有能快速求出前缀和的方法就可以做。

组合数和数论函数的卷积的题现在还是很少的，或许以后任意函数卷数论函数的题会变多吧。

1727

大部分都在题解里，这个题我也在校内模拟赛出过。说一下唐老师题解里没有的部分。

我们要求的东西是把一个数分成若干个数且都不为1的方案数。

显然可以容斥。可以用组合数算出把一个数分成若干个数的方案数，然后差分一下就是那个东西。是O(log^2)的，所以瓶颈在RHO。

1768

这个题思想非常好。这个做法我用在过CF有一场的F上导致了全校一起FST。

这类问题大抵是在区间内询问一个关于值域连续性的问题，允许离线。

一种思路是用不删元素的莫队做，具体是BZOJ的permu。

还有一种思路就是对询问建KDTREE，然后把元素当做操作，按从小到大去操作询问，permu也可以这个做法但是莫队常数要小很多。

1248

这是一个没什么人过的傻逼题。

稍加观察发现F是对称的，就A了。

1303

这个题第一次看到不会做，模拟赛现场打出了。

反正就是容斥，瞎比容斥，然后再用类似于求全1矩阵有多少个的方法，每一行单调栈爆过去算以每个点为四个角的矩形有多少个。

显然一个矩形的右下角在另一个矩形的左上角的右下方才有可能相交。

所以只要算出这样的情况数减去相离包含的关系就行了，这两种都可以很轻松的用隔板法做。

1356

显然形如$4a,9a,16a$换成$a$本质是一样的。

官方题解说法是一个不难想到的结论是构造$a_{1}+a_{2}+...+a_{n}$这样的式子，对于每一个存在出现过倍数的质数$k$，选择$k$集合的一个子集，然后对于这个子集里的$k$，假如$a_{i}$整除偶数个$k$那么系数就是正的，否则就是负的。这样的$2^k$个式子乘起来一定是一个合法解。可以理性愉悦一下，看起来很对我不会证。

然而不是最优解因为会存在某些子集最后弄出来的式子是一样的情况。

根据矩阵那一套理论不难发现只要把那个01矩阵高斯消元一下，2的矩阵的秩次方就是答案，因为上面那个解一定是他的若干次方。

龙哥做到过一个对于20个是素数的互不相同的$a_{i}$要求出那个式子的题，不会啊。

1599

这个题题解里的构造涉及到多项式上一个非常有趣的概念，后面会说。

1211

这个题非常推荐大家写一写。

显然可以对于每个不是其他数幂次的数，对于他的幂次计算贡献。

$n$太大了显然要分段计算。具体方法可以脑补把数论函数求和那个常用的$n,n/2,n/3...,n/n$换成$n,n^{1/2},n^{1/3}...,1$道理是一样的，只有$log(n)$段的。

然后问题转化为一个矩形第i行第j列是$i*j$求不同元素个数。

显然只有行和行之间会重复。而且对于这个题行数是$10^18$但只有$60$列。

一个非常simple的容斥是枚举每一个子集然后搞，但是$2^60$太大了。

写出那个东西之后看一下会发现我们只关心每个子集的$max,min,lcm$。

所以就可以DP了。然后我们就发现状态太多了空间不够。

那么枚举min,对于每个状态只记lcm，从小到大加入元素显然最后一次加的就是max所以直接更新。

就可以O(跑得过)通过这个题了。

----------------------------------------------------------------------------------------------------------------

后面是一些理论性的东西。

说实话我感觉一味地背板子而不深入理解意义不大，稍微考一下那种靠理解的题就GG(典型是UNR2017D1T3)。

先从简单地说起，树状数组。

树状数组为什么能这样搞，我的理解是对于每一个长度为n的序列单点加区间和，都可以补到$2^k$(类似于FFT)然后搞，是一样的。

初赛里会考一个东西叫补码，然后我们就可以发现对于一个$s$,$s$和补码的$lowbit$一定是相同的。

同理因为$s+lowbit$的补码就是$s$的补码减去$lowbit$所以这个过程没有什么奇怪的问题。

那么就不难发现对于任意$i>j$，$i$不断减去$lowbit$,$j$不断加上$lowbit$一定会在某个地方相遇，相遇的地方就是$j$的补码和$i$的LCP。假如看出这个之后再看ZJOI的线段树之后就显得那么自然。

----------------------------------------------------------------------------------------------------------------

数论函数和剩余系。

我的课件已经不知道被我扔到哪里去了，随便侃一侃。

经典的数论函数的求和问题其实杜教筛只需要做$\mu$和$\mu$乘上幂函数的前缀和就行了，因为任意两个函数的卷积前缀和都可以用这两个函数的前缀和在根号时间内算出，所以搞那些花里胡哨的其实都是不需要的。

洲阁筛还是万能，但是感觉某些意义上它限制了数论函数问题的发展，毕竟什么问题都可以用洲阁筛。

LOJ那个xumingkuan出的T3非常有想法，可能这种题和前面说的1211会成为以后问题的主流而不是像现在一样浮于表面。

离散对数唐老师的直播都讲得非常清楚，只要理解了$\rho$的形状都非常好搞，练手可以去做LOJ比赛第一场还是第二场那个G。

高次剩余我博客里有比较详细的说明，不过感觉除了和$FWT$结合并不会考。

----------------------------------------------------------------------------------------------------------------

多项式相关

FFT是求点值大家都知道，但FWT的本质也是求点值，其本质是相同的。

我见到的循环卷积都是转单位根点值之后运算再转回来的，单位根的性质导致它溢出的话会爆到前面来所以可以用来做循环卷积。

FFT和FWT的区别无非是一个是一元的，一个是k元的，一个域长一点，一个域长短一点，一个是一个长n的域，一个是很多长2的域。

（这里我可能有一些名词上的口胡）

换而言之就算给$n$个长$k$的域的多项式运算都是可以做的，而且可以FWT和FFT结合已达到一个不错的效率。

多个域的循环卷积很好处理，和多维FFT类似，只要一维做完以后把这一维当做常量去FFT下一维就行了。

问题是域长假如很奇怪的话就不好搞，域长是k的话就要求k次单位根就很麻烦。

一个不用写高次剩余的做法是设一个$\omega$然后把每一个位置表示成它的$k-1$次多项式爆爆爆。

去年清华集训那个石家庄xxx那个题就可以这么过。

说一下UNR那个T3我的思路，我没记错的话JOHNKRAM是一血，我是第二。

首先要知道FWT本质是求点值，所以一个思路就是快速求出最后的点值。

当然暴力FWT是不行的，

系数里只有一个位置$a$是1的多项式转成点值之后位置$b$的值是-1的$a&b$的1个数次方，只要想到1的2次单位根是-1就好理解。

所以这题每次乘上去的多项式一定是$1+2A$的形式，自然点值一定是$1+2$或者$1-2$取决于$a_{i}&b$的1的个数

现在问题变成对于每个$b$,$a&b$有偶数个1的$a$有多少个，奇数个1的有多少个。

这个可以非常轻松的用一种类似于区间DP的方法解决。

----------------------------------------------------------------------------------------------------------------

一种特殊的二维数点

去年的15人互测，有一个叫线段树的题（我没记错吧）

里面涉及到一种特殊的二维数点，然而我的做法只有耀峰听懂了。。。这里也说一下。

这个二维数点要求矩阵内有多少个点。特点是点的坐标不会相交。也就是括号序列。

考虑那个线段树的模型，从左到右深度的变化可以理解成一个进栈出栈的过程，有多少个元素进栈出栈都在这个时间区间内那么它就是被包含的。

那么显然答案就是出栈操作数-进栈在时间区间之前的，出栈操作数可以直接单点加区间求和，后面的相当于询问区间内栈的最小深度和询问时间区间开始时栈的深度，也可以轻松实现。就好了。

----------------------------------------------------------------------------------------------------------------

那么，结束了？

希望每个人都能被生活温柔以待。