<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_e741c76e7a8c5338cea886f0cd79480a, O_RDWR) failed: No space left on device (28) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  session_start(): Failed to read session data: files (path: ) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/auth.php</b> on line <b>430</b><br />
<div class="error">Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed</div><br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
==== 题面描述 ====
一个长度为 $n$ 的数列 $c$ ，对其赋值为 $0/1$ ，要求 $c_i$ 和 $c_{i+1},c_{i+k}$ 均不能同时为 $1$ 。求所有合法赋值情况下，赋值为 $1$ 的位置的 $w$ 的乘积的和。

$k \le n \le 300$

==== 题解 ====
考虑将序列每行 $k$ 个来变成一个不完整的矩形。这时候我们有两种算法：

第一种：我们考虑直接来轮廓线DP，这样的复杂度是 $O(有效状态数*n)$的。

第二种：我们考虑将其转置一下后再轮廓线DP，但是这时候还需要判断第一行和最后一行之间的合法性，所以复杂度是 $O(有效状态^2*n)$ 的。

这里的有效状态数都是斐波那契级别的，可以近似算作 $O(1.618^{len})$，那么第一种的复杂度就是 $O(1.618^k*n)$ ，第二种就是 $O(1.618^{2n/k}*n)$ 。平衡一下复杂度，考虑按照 $2*sqrt{n}$ 为阈值来分开做，算完时间复杂度是正好够的。

后记：我用那个GNU C++17是会超时的，但是换成GNU C++20那个就很轻松的过了（雾）。