Description

$F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2}$

$E_i~=~\frac{F_i}{q_i}$

对 $1 \leq i \leq n$，求$E_i$的值。

---

模板题

1.定义

设$f(n)$为卡特兰数，则有：

$f(n)=\binom{n}{2n}-\binom{n-1}{2n}$

存在递推式：

$f(n)=\sum_{i=0}^{n-1}\binom i n\binom {n-i-1} n$

数论函数&&莫比乌斯反演&&杜教筛

Description

现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 1 到 n 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 1 到路由器 n 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1 到路由器 n 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1 和 n 直接相连的链路。

计数问题 Ⅰ

1.概述

折半搜索，又称meet in the middle，通常是把不能直接做的题目分成两半。

把这两半分别搜索。

Description

有 N 个村庄坐落在一条直线上，第 i(i>1) 个村庄距离第 1个村庄的距离为 $$D_i$$。需要在这些村庄中建立不超过 K个通讯基站，在第 i个村庄建立基站的费用为 $$C_i$$。如果在距离第 i 个村庄不超过 $$S_i$$ 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 i 个村庄没有被覆盖，则需要向他们补偿，费用为 $$W_i$$。现在的问题是，选择基站的位置，使得总费用最小。

---

2020.06.27

菜到抠，连数字三角形都写挂了

$O(nlogn)$求LIS&LCS长度

你怎么连这个都不会qwq