[QOJ10037] Build Well

感觉好牛的题。

题目链接。

题意

你现在需要建造一个周长为 的水井，现在有 种可用的砖块长度，第 种为 。

水井的砖块由很多层构成，如果存在相邻两层的某个位置，在这两层同时是砖缝，我们就认为这个水井是不稳固的。

构造一组放置砖块的方案，每一种砖块都可以使用任意多次。显然只需要构造相邻两层的方案即可。

题解

首先考虑如果只需要建造一层水井怎么做，显然直接 dp 优化一下能做到 。

那么假设现在存在一组建造一层水井的方案，并且这个方案没有使用长度为 的砖块，问题就已经解决了。

因为我们可以直接把这个方案复制一遍，然后往右偏移 。

假设不存在这样的方案，那么如果此时长度为 的方案还不是可用的，显然整个问题无解。

现在我们考虑在如下限制下做出构造：上下两层使用的砖块顺序完全相同，并且偏移为 ，但引入一种全新的“组合块”。

一个组合块为一个长度为 的砖块加上不超过 个长度为 的砖块组成。

在第一行，其排列方式为先放长度为 的砖块，再放长度为 的砖块，第二行先放 再放 。

假如这样能跑出一组解，那么整个问题就结束了。现在我们要证明若整个问题有解，则存在一组这样的构造方式。

首先考虑这组合法的方案存不存在上下偏移差为 的位置，如果没有的话就转到至少有一个位置。

现在整个环有至少一个上下差为 的位置，把整个环分成了若干份，现在我们对这些部分分别进行调整。

对于某一个部分来说，若其现在的方案中某一行没有使用长度为 的砖块，那么直接把另一行调整一下就好了。

否则，设两行长度均为 ，并且其中使用砖块较少的一行使用了 块砖，那么这一行会产生 个缝。

我们可以得到 ，即 。

在考虑，设这一行有 个长度 的砖块，则这一行有 个长度为 的砖块。所有长度 的砖块长度和为 。

考虑这些长度 的砖块最多能和多少长度为 的砖块进行组合，答案为 。

也就是说我们完全可以用这些砖块拼成组合块然后进行构造。证毕。

时间复杂度 。

update：qoj 上 T 了，你需要分治 NTT。