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

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

题面 传送门： 洛咕 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*\sum_{i>j}\frac{q_i}{(i-j)^2}$ 左右同时除以$q_j$ $E_j=\sum_{…

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘，复杂度必然是$O(n^2)$的，而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先，我们得先了解如何表示一个多项式。显然，我们最传统的方法表示多项式就是表示它的系数就好。但是，如果我们用系数来计算两个多项式相乘，复杂度无论如何都是$O(n^2)$的。因此，我们引入点值表示法。 补充资料：什么是点值表示 设A(x)是一个n−1次多项式，那么把n个不同的x代入，会得到n个y。这…