题目大意：给定一个$n$个点的凸包，要求从中选出$k$个点构成一个子凸包，求子凸包的最大周长

发现对于子凸包来说，只有一条边是从大标号点连向小标号点，这一条边容易单独考虑，而对于剩下的$k-1$条边可以用DP处理

设$E_m[i][j]$表示从$i$点经过$m$条边到达$j$的最长距离，容易得到转移方程 $$ E_{a+b}[i][j]=\max\limits_{i\leq k\leq j}(E_a[i][k],E_b[k][j]) $$ 该转移方程可以使用矩阵快速幂优化，复杂度$O(n^3logn)$

上述转移方程是经典区间DP，猜想其具有决策单调性

设最优的$E[i][j]$由$k=V[i][j]$转移而来，对$V[i][j]$打表，若矩阵的每一行每一列都单调，则满足决策单调性

根据决策单调性的结论，记录每一次转移的$V[i][j]$，直接将转移方程中的$i\leq k\leq j$改为$P[i][j-1]\leq k\leq P[i+1][j]$即可优化至$O(n^2logn)$

题目大意：给定一个有厚度的凸多边形围墙和一个点光源，问围墙内有多少面积有光

已知凸包外围，利用半平面交可以得到凸包内围

若只有凸包内围顶部，将点光源与凸包内围顶部连线，与地面交成一个凸包，则这个凸包为照亮区域

接着考虑凸包内围底部，实际照亮区域为凸包内围底部与照亮区域的交，半平面交可以解决

可以提前处理一些特殊情况，比如点光源的高度比围墙低

对于所有的$0\leq i\leq n$，求长度为n的字符串中恰好出现了i个”bit” 子串的字符串数量

考虑容斥。首先容易想到，先在字符串中确定一些“bit”，然后其他位置任选，于是设$G[i]$表示在字符串中先确定$i$个“bit”，其他位置任意的方案数

利用隔板法以及一些组合技巧，可以得到 $$ G[i]=C_{n-2i}^i*26^{n-3i} $$

设字符串中恰有$i$个“bit”的方案数为$F[i]$，利用二项式反演可以得到 $$ F[i]=\sum_{j=k}^{n/3}(-1)^{j-k}C_j^kG[j] $$

这是经典$NTT$形式，将组合数拆开，构造系数即可$NTT$优化

移项预处理矩阵即可
时间复杂度 $O(nkd)$

最小二乘法 $$ \hat{a}=\dfrac{\sum_{i-1}^n(x-\bar x)(y-\bar y)}{\sum_{i=1}^n(x-\bar x)^2}\\ \hat b = \bar y - \hat a\bar x $$ 时间复杂度 $O(n)$