沿街有 n 栋房子，我们需要用 3 种颜色中的一种给每栋房子上色，但有 2 个限制：
N 是偶数并且是唯一的输入。计算以 1e+5 为模的可能颜色的数量。
这很可能是 dp，但事实证明这些州对我来说很困难。我尝试做 dp[i][j][k] ，当对称颜色为 k 时，我们用第 i 个颜色绘制第 i 个房子，但随后问题变得相当循环，我不知道从哪里开始。
N/2 + 1st house 既有前n/2个房子，也有对称的房子，一般来说，如果我们固定前n/2个房子中的任何一个房子的颜色，就有 2^(n/2 - 1) 种着色方式总共 n/2 栋房屋。那么仍然不清楚如何进入进一步的状态，因为即使我可以计算 n/2th + 1st house 的着色数量（当 n/2th 颜色固定时，对于任何颜色，2^(n/2 - 1) ），我不一定会对更多房屋的对称性施加限制。
我注意到的另一件事是，如果我们对这排房子的两端进行着色（即第 1 和第 n），那么我们会受到限制，但问题在某种程度上减少到大小 n - 2，我们再次需要为第 2 和第 n-2 房子着色等等。所以也许有一些基于这种状态转换的解决方案。
我也尝试过包含/排除，仅第一个约束并不难计算：3 * 2^(n - 1)，但第二个约束的否定很难计算：超过的着色数量1 栋房子，其对称的房子颜色相同，等等，但它并没有完全通向任何地方。
非常感谢任何帮助
如果 N 是偶数，那么在该行的中心有两座相邻且对称的房子。由于相邻性（规则 1），它们必须具有不同的颜色；由于对称性（规则 2），它们必须具有相同的颜色。因此，无论可用颜色的数量是多少，都不存在这种着色，并且对于任何 N，答案都是 0。您可以通过
N==2