zcmimi's blog
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了

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

点击跳转

  1. 金神石的块数必须是6的倍数 g(x)=1+x^6+x^{12}+...=\frac 1{1-x^6}
  2. 木神石最多用9块 g(x)=1+x+x^2+...+x^9=\frac{1-x^{10}}{1-x}
  3. 水神石最多用5块 g(x)=1+x+x^2+...+x^5=\frac{1-x^6}{1-x}
  4. 火神石的块数必须是4的倍数 g(x)=1+x^4+x^8+...=\frac 1{1-x^4}
  5. 土神石最多用7块 g(x)=1+x+x^2+...+x^7=\frac{1-x^8}{1-x}

  6. 金神石的块数必须是2的倍数 g(x)=1+x^2+x^4+...=\frac 1{1-x^2}

  7. 木神石最多用1块 g(x)=1+x=\frac{1-x^2}{1-x}
  8. 水神石的块数必须是8的倍数 g(x)=1+x^8+x^{16}+...=\frac 1{1-x^8}
  9. 火神石的块数必须是10的倍数 g(x)=1+x^{10}+x^{20}+...=\frac 1{1-x^{10}}
  10. 土神石最多用3块 g(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}

\frac 1{1-x^6}\cdot\frac{1-x^{10}}{1-x}\cdot\frac{1-x^6}{1-x}\cdot\frac 1{1-x^4}\cdot\frac{1-x^8}{1-x}\cdot\frac 1{1-x^2}\cdot\frac{1-x^2}{1-x}\cdot\frac 1{1-x^8}\cdot\frac 1{1-x^{10}}\cdot\frac{1-x^4}{1-x}

=\frac1{(1-x)^5}

=\sum_{i=0}^\infty {i+4 \choose 4}x^i

\sum_{i=0}^\infty {i+k-1 \choose k-1}x^i=\frac1{(1-x)^k}

n项的系数是{n+4 \choose 4}需要FFT或NTT

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

点击跳转

29/73
Search
search