zcmimi's blog

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

avatar
zc
2020-02-18 21:05:00
查看原题

点击跳转

avatar
zc
2020-02-18 17:27:00
查看原题

点击跳转

  1. 快速幂
  2. Exgcd

    xy \equiv z \pmod p

    yx+pb = z

    可以用Exgcd求解

  3. bsgs

    求解关于x的方程:

    y^x \equiv z \pmod p

    其中\gcd(y,p)=1

    解法:

    x=am-b

    那么y^{am} \equiv z \cdot y^b \pmod p

    右边:

    枚举b的取值[0,m-1],计算右边的值,存入哈希表

    左边:

    枚举可能的a,也就是[1,m],若左边的值在哈希表中出现过,那么当前a合法

    不难证明当m=\sqrt p的时候复杂度最优,\Theta(\sqrt p)

avatar
zc
2020-02-16 18:54:00
查看原题

点击跳转

f[i,j]表示用完了前i种油漆,有j对相邻且同色的木块

考虑怎么转移:

要将第i种颜色的木块分两种情况插入:

  1. 设其中a个插到之前弄好的木块中间(无序)

  2. 设另外b个插在同色木块中间

其中有a-b组满足插空放且不相邻

f[i,j]=\sum f[i-1,j-(c_i-a-b)]\times {c_i-1 \choose a-1} \times {j \choose b} \times{S_{i-1}+1-j \choose a-b}

{c_i-1 \choose a-1}表示a个的方案数

{j \choose b}表示b个的方案数

{S_{i-1}+1-j \choose a-b}表示a-b个插进去的方案

avatar
zc
2020-02-16 15:21:00
查看原题

点击跳转

f(i,k)表示前i位置,操作k次,最多剩下多少玉米

每一次的拔高操作区间右端点一定是最右边的玉米

f(i,k)=max_{j<i}(f(j,k-t))+1,a_i+t\ge a_j

直接枚举\mathcal{O(n^2k^2)}会超时,我们得想个办法优化

可以考虑用二维树状数组优化

优化为只需要两个树状数组

https://guodonglovesoi.blog.luogu.org/scoi2014-fang-bo-bo-di-yu-mi-tian

avatar
zc
2020-02-15 20:34:00
查看原题

点击跳转

双连通分量缩点后得到的树的直径就是答案

avatar
zc
2020-02-14 14:21:00
查看原题

点击跳转

对于第二问:

看到数据范围可以想到矩阵快速幂求斐波那契数列

矩阵乘法具有分配率: AC+BC=(A+B)C

我们可以想到用线段树维护矩阵区间乘

avatar
zc
2020-02-14 00:06:00
查看原题

点击跳转

首先可以dfs处理出所有路径的重要度(路径两端子树大小乘积)

然后就是树型dp处理出每个点影响的范围的重要度总和

最后取最大值就可以了

f(dis,x)表示与x距离不超过dis的所有路径的重要度

f(1,x)=\sum val(edge)

f(k,x)=\sum f(k-1,to)-f(k-2,x)

avatar
zc
2020-02-13 22:22:00
查看原题

点击跳转

直接模拟

复杂度\mathcal{O}(\frac n1 + \frac n2 + , ... + \frac nn)=\mathcal{O}(n \log n)

avatar
zc
2020-02-08 22:00:00
查看原题

点击跳转

假设我们要求的是A\cdot B \equiv 1 \pmod{x^n},

我们已经求出了B'满足A\cdot B' \equiv 1 \pmod{x^\frac n2}

\because A\cdot B \equiv 1 \pmod {x^n} \\ \because A\cdot B' \equiv 1 \pmod{x^\frac n2} \\ \therefore A \cdot (B-B') \equiv 0 \pmod{x^\frac n2} \\ \therefore B-B' \equiv 0 \pmod{x^\frac n2} \\ (B-B')^2 \equiv 0 \pmod{x^n} \\ B^2-2BB'+B'^2 \equiv 0 \pmod{x^n} \\ \therefore A(B^2-2BB'+B'^2) \equiv 0 \pmod{x^n} \\ AB^2-2ABB'+AB'^2 \equiv 0 \pmod{x^n} \\ \because A\cdot B \equiv 1 \pmod {x^n} \\ \therefore B-2B'+AB'^2\equiv 0 \pmod{x^n} \\ B\equiv 2B'-AB'^2 \pmod{x^n}

于是我们可以用倍增+NTT解决(复杂度\mathcal{O(n \log^2 n)})

avatar
zc
2020-02-08 14:58:00
查看原题

点击跳转

E_i=\frac{F_i}{q_i}=\sum_{j=1}^{i-1}\frac{q_j}{(i-j)^2}-\sum_{j=i+1}^n \frac{q_j}{(j-i)^2}

f_i=q_i,g_i=\frac 1{i^2},f_0=0,g_0=0

E_i=\sum_{j=1}^i f_j\cdot g_{i-j}-\sum_{j=i}^n f_j\cdot g_{j-i}

可以发现前半部分是卷积的形式

我们来考虑后半部分

\sum_{j=i}^n f_j\cdot g_{j-i} \\ =\sum_{j=0}^{n-i} f_{i+j}\cdot g_j

t=n-i,f'_i=f_{n-i}

=\sum_{j=i}^t g_j\cdot f'_{t-i}

也成功转化为卷积的形式

可以开始愉快地使用FFT了

22/66
Search
search