zcmimi's blog
avatar
zc
2020-08-25 17:41:00
查看原题

点击跳转

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

细节: 如果从n开始有连续一段空白,那么这段空白要去掉

转换后可以发现只需要m+1张牌就可以

考虑每次"亵渎"的贡献

第一次"亵渎"的贡献就是\displaystyle \sum_{i=1}^n i^k剪掉空位的贡献

在空位p上使用"亵渎",有贡献的位置: [p+1,n],贡献为\displaystyle \sum_{i=1}^{n-p} i^k

减去空位多算的贡献即可

求自然数幂和可以考虑拉格朗日插值,递推法,伯努利数等

avatar
zc
2020-08-08 20:19:00
查看原题

点击跳转

\begin{aligned} &\quad\sum_{i=1}^n \gcd(i,n)^x lcm(i,n)^y \\ &=\sum_{i=1}^n \frac{in}{lcm(i,n)}^x lcm(i,n)^y \\ &=\sum_{i=1}^n (in)^x lcm(i,n)^{y-x} \\ &=\sum_{i=1}^n (in)^x \frac{in}{\gcd(i,n)}^{y-x}\\ &=\sum_{i=1}^n (in)^y \gcd(i,n)^{x-y} \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^n i^y [\gcd(i,n)=d] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y [\gcd(i,n)=1] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y \sum_{k|i,k|n}\mu(k) \\ &=n^y\sum_{d|n} d^{x-y}\sum_{k|\frac nd}\mu(k)\sum_{i=1}^{n/dk} (idk)^y \\ &=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=1}^{n/dk} i^y \end{aligned}

\displaystyle S_k(n)=\sum_{i=1}^{n-1}i^k,可以看做一个y+1次多项式,假设求出后每一项系数为t_i

=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^yS_y(\frac n{dk}) \\ =n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=0}^{y+1}t_i(\frac n{dk})^i \\ =n^y\sum_{i=0}^{y+1}t_i \sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i

其中,设\displaystyle Z(n)=\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i ,

可以看成f(d)=d^x,g(d)=\mu(d)d^y,h^i(d)=d^i这三个积性函数的狄利克雷卷积

卷积后还是积性函数,且狄利克雷卷积满足交换律,只有当x=1x=p^k\mu(x)\ne 0

\begin{cases} Z(1)=1\\ Z(p)=p^x-p^y+p^i\\ Z(p^k)=(f * h^i)(p^k)-(f * h^i)(p^{k-1}) \cdot p^y \end{cases}

其中\displaystyle (f * h^i)(p^k)=\sum_{i+j=k} f(p^i)\cdot h^i(p^j)

使用Pollard-Rhon分解质因数,枚举每个质因子(包括次幂),然后狄利克雷卷积计算答案

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

给出n个点m条边的无向图,每条边u\leftrightarrow v有两个权值a,b

q个询问,给出u,v,A,Bu,v间是否存在路径\max\{a\}=A\max\{b\}=B

先考虑最暴力的做法:

把所有符合条件的边(a\le A,b\le B)添加到并查集,

然后判断最大值是不是A,Bu,v是否连通

接着对边排序、回滚莫队,使用按秩合并并查集(可撤销并查集)

m条边按a进行排序

对询问按b进行排序

m条边进行分块

对每个块处理符合a大于等于该块\max\{a\}的询问

把当前块前面的点按照b排序(使b单调递增)

开始处理询问:

当前块前面的点的b是单调递增的,而a一定符合条件 ,所以可以一直右移指针添加符合条件的边

然后枚举块中的边,添加符合当前询问的边,得到当前询问答案,回滚,删掉当前询问添加的边

下一个询问

处理完当前块后,暴力清空并查集

分块大小为\sqrt{m\log n}时复杂度最优

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

分块好题

\gcd有个性质: 一旦变动则小于原来的\frac 12(最小的质因子为2)

那么总共最多\log_2 n个不同的\gcd

每个块记录的信息:

  • 块内前缀gcd
  • 块内前缀xor和

然后对块内元素按前缀xor和排序

修改操作: 修改对应元素,并重构元素所在块

查询操作:

枚举每个块,若前缀gcd不变,则直接在排序好的元素中二分查找

否则枚举判断

复杂度O(n\sqrt n \log n)

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

设通配符的数值为0,定义匹配函数C(x,y)=[A(x)-B(y)]^2A(x)B(y),那么\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)

按照套路,翻转A串得到S串:

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2S(m-i+1)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}S(m-i+1)^3B(x-m+i+1)+\\ &\quad\sum_{i=0}^{m-1}B(x-m+i+1)^3S(m-i+1)-\\ &\quad2\sum_{i=0}^{m-1}S(m-i+1)^2B(x-m+i+1)^2 \end{aligned}

写为卷积形式:

\displaystyle P(x)=\sum_{i+j=x}S(i)^3B(j)+S(i)B(j)^3-2S(i)^2B(j)^2

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

  1. 区间加
  2. 求序列最大前缀和

区间加,相当于前缀和加上一个等差数列

而等差数列加上一个等差数列还是等差数列

考虑将每个位置的前缀和转化为一个一次函数kx+b

分块,对每个块维护一个上凸壳单调栈,可以二分找到最大值

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

n个人和m种物品,第i种物品有a_i个,同种物品之间没有区别。现在要将这些物品分给这些人,使得每个人至少分到一个物品

每个同学都必须至少分得一个

可以通过 恰好没有同学没有分得 来反演

f_i为钦定i个人没有分到,

钦定的方案数为{n\choose i},这时第j种物品分给n-i个人,使用隔板法,方案数为{n-i+a_j-1\choose n-i-1}

f_i={n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1}

g_i为恰好i个人没有分到,反演:

g_k=\sum_{i=k}^n(-1)^{i-k}{i \choose k}f_i

那么:

\begin{aligned} ans &=g_0\\ &=\sum_{i=0}^n(-1)^if_i\\ &=\sum_{i=0}^n(-1)^i{n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1} \end{aligned}

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

异或一个数两次,可以抵消

我们可以给区间中所有相同的数都赋一个新的随机数值,防止异或时出现干扰

pre_ii位置的数上一次出现的数,v_i为位置i新赋值的数,S_i为异或前缀和

若区间[l,r]中所有数出现的数出现的次数是奇数,那么S_r\oplus S_{l-1}等于\{v_i|pre_i<x,i\in [l,r]\}的异或和

枚举r,设p_x\{v_i|pre_i<x,i\in [x,r]\}异或和

那么相当于求满足S_r\oplus S_{x-1}\oplus p_x=0

r变为r+1,\{p_i|i\in [pre_{r+1}+1,r]\}异或上v_{r+1}

问题也就转化为了: 区间异或,区间查询某个数出现次数

使用分块+hash解决

14/73
Search
search