zcmimi's blog

categories/刷题记录/共653篇文章

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
查看原题

点击跳转

题意:

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

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

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

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

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

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
查看原题

点击跳转

题意:

给出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
查看原题

点击跳转

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370149

题意:

给一个序列A,要求支持以下操作:

  1. 区间乘

  2. 区间里所有数都变成自己的k次幂

  3. 求区间乘积(mod 10000000007)

由于模数是质数,所以可以将每个数都变成原根的次幂

这样区间乘转化为区间加,区间次幂转化为区间乘,求区间乘积转化为求区间和

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解决

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 19:14:00
查看原题

点击跳转

f(n)=\sum_{i=0}^n \sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix} 2^j j!

考虑到i<j\begin{Bmatrix}i\\j\end{Bmatrix}=0 :

f(n)=\sum_{j=0}^n 2^j j! \sum_{i=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}\\ =\sum_{j=0}^n 2^j j! \sum_{i=0}^n \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!}\\ =\sum_{j=0}^n 2^j j! \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{\sum_{i=0}^n (j-k)^i}{(j-k)!}

\displaystyle g(k)=\frac{(-1)^k}{k!}, h(k)=\frac{\sum_{i=0}^n k^i}{k!}=\frac{k^{n+1}-1}{(k-1)k!} ,

特别的: h(0)=1,h(1)=n+1

那么

f(n)=\sum_{j=0}^n 2^j j! (g\times h)(j)

卷积后即可计算

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

sa的前缀和,Ss的前缀和

\begin{aligned} ans &=\sum_{i=l}^r \sum_{j=i}^n s_j-s_{j-i}\\ &=\sum_{i=l}^r\left(\sum_{j=i}^n s_j-\sum_{j=i}^ns_{j-i}\right)\\ &=\sum_{i=l}^r\left(\sum_{j=1}^n s_j - \sum_{j=1}^{i-1} s_j -\sum_{j=0}^{n-i}s_j\right)\\ &=\sum_{i=l}^r ( S_n-S_{i-1}-S_{n-i})\\ \end{aligned}

线段树维护S即可,如何维护S?

假设[l,r]区间加v,

g_i=1+2+3+\dots+i=\frac{i(i+1)}2

假设i\in[l,r],那么S_i加上v\times g_{r-i+1}

假设i\in[r+1,n],那么S_i加上v\times g_{r-l+1} + v\times(i-r)(r-l+1)

7/66
Search
search