传送门给定一个长度为\(n\)的木板，木板上有\(m\)个标记点，距离木板左端点的距离分别为\(X_i\)，现在你需要在木板上放置一些不相交正方形，正方形需要满足正方形的边长为整数正方形底面需要紧贴木板正方形不能超出木板，正方形要将所有的木板覆盖标记点的位置不能是两个

PlacingSquares关键是将问题从抽象的“正方形面积”转为具象的形式：一段长度为\(d\)的区间，有两个不同的小球要放进去，则总放置方案就是\(d^2\)，且不同的区间间方案是通过乘法原理结合的，刚好是题目中\(\prodd^2\)的形式。于是我们可以设计DP：设\(f_{i,j}\)表示前\(i\)个

想了一会然后看题解，翻到日文题解然后又关了，然后突然会了，怎么回事第一眼生成函数！做不了。考虑经典拆贡献方法，把平方的贡献变成从区间中选两个数的方案数。这样我们可以用一个DP来计数。设\(f_{i,j}\)表示到了第\(i\)格，已经选了\(j\)个数的方案数。如果没有限制，那么就直

模型转化题，转化不出来就白给。可以把题目的条件翻译成以下组合语言：有一排\(n\)个格子，你要在其中插入若干个隔板将其隔成若干段有\(m\)个特殊格子\(a_1,a_2,\dots,

AT2371[AGC013E]PlacingSquares设\(f_i\)表示考虑到第\(i\)个点的贡献之和且不考虑坏点。不难发现转移方程为\(f_n=\sum_{i=0}^nf_i\times(n-i)^2\)则当第\(n