题面 传送门：洛咕 Solution 这题比这题不懂简单到哪里去了 好吧，我们来颓柿子。 为了防止重名，以下所有柿子中的$x$既是题目中的$d$ 为了方便讨论，以下柿子均假设$b>=a$ 为了方便书写，以下除号均为向下取整 题目要求的显然是： $\large \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=x]$ 根据套路，我们这里要先把这个$x$除掉 $...

题面 传送门：洛咕 Solution 推到自闭，我好菜啊 显然，这题让我们求： $\large \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$ 根据套路，我们可以把判断是否为质数改为枚举这个质数，有： 为了方便枚举，我们在这里假设有$m>n$ $\large \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k\in...

蒟蒻尚在学习，请各位dalao不要相信本文的任何一个字，包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下： $f\cdot g(n)=\sum_{dn}f(d)\cdot g(\frac{n}{d})$ 也可以写作： $f\cdot g(n)=\sum_{i\cdot j=n}f(i)\cdot g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式...

什么是欧拉函数 记欧拉函数为$\varphi(x)$表示比$x$小且与$x$互质的数的个数。 怎么算欧拉函数 通项公式:$\varphi(x)=x*\prod(1-\frac{1}{p_i})$ ($p_i$为$x$的质因数) 因为欧拉函数是一个积性函数，因此我们可以用欧拉筛(线性筛)在$O(n)$的时间内预处理出来：具体证明请见后文 123456789101112131415161718...

题面 传送门：洛咕 Solution 调得我头大，我好菜啊 好吧，我们来颓柿子吧： 我们可以只旋转其中一个手环。对于亮度的问题，因为可以在两个串上增加亮度，我们也可以看做是可以为负数的。 所以说，我们可以假设我们旋转$B$串，上下要加上的亮度差为$p$,可以直接拍出一个最暴力的柿子： 设$f(x)$表示$B$串以$x$为开头的差异值，有： $f(x)=\sum_{i=0}^{x-1}(B[...

题面 传送门：洛咕 Solution 这题我写得脑壳疼，我好菜啊 好吧，我们来说正题。 这题…emmmmmmm 显然KMP类的字符串神仙算法在这里没法用了。 那咋搞啊（或者说这题和数学有半毛钱关系啊） 我们考虑把两个字符相同强行变为一个数学关系，怎么搞呢？ 考虑这题是带通配符的，我们可以这样设: $C(x,y)=(A[x]-B[y])^2*A[x]*B[y]$ 因此，我们可以看出两个字符一...

题面 传送门： 洛咕 BZOJ Solution 写到脑壳疼，我好菜啊 我们来颓柿子吧 $F_j=\sum_{i<j}\frac{q_i*q_j}{(i-j)^2}-\sum_{i>j}\frac{q_i*q_j}{(i-j)^2}$ $q_j$与$i$没有半毛钱关系，提到外面去 $F_j=q_j*\sum_{i<j}\frac{q_i}{(i-j)^2}-q_j*\...

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘，复杂度必然是$O(n^2)$的，而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先，我们得先了解如何表示一个多项式。显然，我们最传统的方法表示多项式就是表示它的系数就好。但是，如果我们用系数来计算两个多项式相乘，复杂度无论如何都是$O(n^2)$的。...

题面 洛咕 CodeForces Solution 这题写得我脑壳疼，我好菜啊 . 显然，这题让我们求$\sum_{i=1}^{n}C_n^i\times i^k$ 这个$i^k$让人浑身难受，我们可以考虑把它搞掉，能搞掉某个数的幂次方的有啥？本蒟蒻只会第二类斯特林数。 . 所以说我们无脑把第二类斯特林数带进去再说： $\sum_{i=1}^{n}C_n^i\times \sum_{j...

本菜鸡尚未学会第二类斯特林数，请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。 Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来...