zcmimi's blog

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

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

点击跳转

能凑出的钱: 使用多重背包(二进制优化)

找零: 使用完全背包

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

点击跳转

多重背包优化模板

avatar
zc
2020-02-25 17:16:00
查看原题

点击跳转

bsgs模板题

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

点击跳转

我们要做的是强行将式子转换为bsgs能求解的形式(求y^x\equiv z \pmod p)

X_{i+1} \equiv aX_i+b \pmod p \\ X_{i+1} + \frac ba \equiv aX_i+b+\frac ba \pmod p \\ aX_{i+1} + b \equiv a^2X_i+ab+b \pmod p \\ X_{i+2} \equiv a^2X_i+ab + b \pmod p

继续往下推,并根据等比数列的公式可以得到:

X_i \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p

带入t\equiv X_i \pmod p,得

t \equiv a^{i-1}X_1+\frac{b(1-a^{i-1})}{1-a} \pmod p \\ (1-a)t \equiv (1-a)a^{i-1}X_1+b(1-a^{i-1}) \pmod p \\ t-at \equiv a^{i-1}(X_1-aX_1)+b-b\cdot a^{i-1} \pmod p \\ a^{i-1}(X_1-aX_1-b)\equiv t-at-b \pmod p \\ a^{i-1}\equiv \frac{t-at-b}{X_1-aX_1-b} \pmod p

成功强行转换

可以用bsgs求解了!

还没完,要考虑一下几种特殊情况:

  1. X_1=t

    第一天就可以读到

  2. a=1

    题目变为X_1+kb \equiv t \pmod p

    因为p是质数,所以可以直接用费马小定理求逆元

    b=0时无解

  3. a=0

    判断b=t

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

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

21/66
Search
search