给定一个长度为 \(n\) 的木板，木板上有 \(m\) 个标记点，距离木板左端点的距离分别为 \(X_i\)，现在你需要在木板上放置一些不相交正方形，正方形需要满足
-
正方形的边长为整数
-
正方形底面需要紧贴木板
-
正方形不能超出木板，正方形要将所有的木板覆盖
-
标记点的位置不能是两个正方形的交界处
一种合法的正方形放置方案的贡献为所有正方形面积的乘积，也就是为 \(\prod\limits_{i=1}^k a_i^2\)，\(a_i\) 为正方形的边长。
请你求出所有合法方案的贡献之和，答案对 \(10^9+7\) 取模。
\(n \leq 10^9\)，\(m \leq 10^5\)。
问题描述不好处理，我们可以这么转化问题：
有 \(n\) 个格子，要在格子之间放隔板。同时要在每一个隔出来的段里的格子放一个黑球和一个白球，允许球重叠。求方案数。
（这里放黑白球的方案数对应了原问题的平方）
\(dp_{i,j}\) 表示前 \(i\) 个格子，从上一个隔板到格子 \(i\) 放了 \(j\) 个球的方案数。对不允许在左侧放隔板的格子和允许放隔板的分别写转移方程。
普通格子：
-
\(dp_{i+1,0}=dp_{i,0}+dp_{i,2}\)。若 \(i,i+1\) 之间不放隔板，方案数 \(dp_{i,0}\)；否则方案数 \(dp_{i,2}\)；
-
\(dp_{i+1,1}=2dp_{i,2}+(2dp_{i,0}+dp_{i,1})\)。若 \(i,i+1\) 之间放隔板，要使 \([i+1,i+1]\) 这个区间有一个球，有两种可能（黑球白球），再乘上上一段的方案数 \(dp_{i,2}\)；如果不放隔板，可能是之前没有，在 \(i+1\) 放了一个，也可能是之前就有了。
-
\(dp_{i+1,2}=dp_{i,2}+(dp_{i,0}+dp_{i,1}+dp_{i,2})\)。同理分析。
禁止格子：
-
\(dp_{i+1,0}=dp_{i,0}\)。
-
\(dp_{i+1,1}=2dp_{i,0}+dp_{i,1}\)。
-
\(dp_{i+1,2}=dp_{i,0}+dp_{i,1}+dp_{i,2}\)。
用矩阵快速幂即可。
标签：AGC013E,木板,格子,隔板,方案,Placing,正方形,Squares,dp From： https://www.cnblogs.com/FLY-lai/p/18153514