蒟蒻尚在学习,请各位dalao不要相信本文的任何一个字,包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下: $\large f*g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也可以写作: $\large f*g(n)=\sum_{i*j=n}f(i)*g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式暴力计算,枚举$i$即可,复杂度$O(\sqrt{n})$ 这里就不上代码了,跟暴力枚举质数长得基本上一…
蒟蒻尚在学习,请各位dalao不要相信本文的任何一个字,包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下: $\large f*g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也可以写作: $\large f*g(n)=\sum_{i*j=n}f(i)*g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式暴力计算,枚举$i$即可,复杂度$O(\sqrt{n})$ 这里就不上代码了,跟暴力枚举质数长得基本上一…
题面 传送门:洛咕 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_{…
COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.
Theme Kratos Made By Seaton Jiang