zcmimi's blog

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

avatar
zc
2020-09-02 16:45:00
查看原题

点击跳转

思路还算挺神奇的

题意:

\sum C_i=k,要让\sum \dfrac{A_i}{C_i}最小

T_i=\dfrac{A_i}{C_i}

假设我们每次要给一个C_i加一,那么\Delta T_i=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1},

我们要让\Delta T_i尽可能大

这样一直加一到最后,会让所有\Delta T_i趋近于相同

\begin{aligned} \Delta T_i &=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1}\\ &=\dfrac{A_i}{C_i(C_i+1)}\\ &=\dfrac{A_i}{C_i^2+C_i} \end{aligned}\\ C_i^2+C_i-\dfrac{A_i}{\Delta T_i}=0\\ C_i=\dfrac{-1+\sqrt{1+\frac{4A_i}{\Delta T_i}}}2

由于\Delta T_i是单调的,\Delta T_i越小,答案越小

所以我们可以二分\Delta T_i,并倒推得出C_i

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种物品,第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)

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

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

6/65
Search
search