Should We Adocate Artificial Intelligence?Nowadays, with the development of technology, AI is becoming increasingly popular. However, views to AI varies. What makes people’s opinions divided is that w

每次在做数学的时候（尤其是组合排列），都深深地感受到一种无力感............一种看完题解感觉自己跟傻*一样地无力感............

这道题最难的其实是想到把【构造一个上升序列】转化为【构造一个差分序列】（当然我是想不到的，所以看了题解的一部分）。了解此思路下的我经过一顿推公式之后依旧只推出了 30pts 的暴力公式和代码，然后看了题解豁然开朗，所以决定写一篇题解来说说暴力和正解的思路。

因为当上一个状态转移到当前状态时，它会左移一位，并且挤掉最左边一位的状态。那么上一个状态的最左边的那一位就有。又发现当前行状态只与上一行状态有关，所以这就相当于。由于它是一个环形花园，因此我们要枚举最初始。（相当于转一圈转回来了），将其累加即可。转移时再判断上一个状态是否合法，即。个花圃的状态固定时，它的贡献就是。这又是在转移方面优化，所以可以想到用。次方后，再乘以初始状态矩阵就好了。还是因为它是

像这种字符串匹配的题，状态设计里一定有一维代表目前匹配到了第。只需要枚举所有状态，然后看看有哪些状态中。位的字符串中，还有哪些可以匹配上第。的可能的字符，然后看看有哪些。的意思就是，当前已经匹配第。假设能匹配的字符串的状态为。，我们就枚举下一个位置。，那么我们就可以转移。，转移不到下一个状态。

虽然是一道非常基础的状压dpdpdp（在洛谷上甚至是道驴蹄），但是我调了两个晚自习，最后发现是竟然是状态设计有问题。所以在此篇题解中，我不但会说出正确做法，还会说出原本的代码错在哪里。以警醒自己状态设计正确的重要性。

别人说这是道简单题，随便搞搞就过了。但我并不觉得（光状态设计第一步就被卡住了），pdf 了。颓题解了，写篇题解谢罪。

虽然是一道比较好想的状压dpdpdp，但是它深深使我我感受到【简洁而快速的二进制操作】对状压dpdpdp的重要意义。

需要。