求解满足相邻异色与对称异色约束的偶数n房屋染色方案数

问题描述 #

有n栋房屋（n为偶数），使用3种颜色为每栋房屋染色，需满足以下两个约束：

• 相邻房屋颜色不同；
• 对称位置的房屋颜色不同（即第i栋与第n-i+1栋颜色不同）。
  要求计算合法染色方案数对1e5取模的结果。

核心解法：分阶段动态规划 #

由于n是偶数，我们可以将房屋按对称对分组：第1栋与第n栋为第1对，第2栋与第n-1栋为第2对，……，第n/2栋与第n/2+1栋为第k对（k = n/2）。通过逐对处理这些分组，就能避免你之前遇到的循环问题。

状态设计 #

定义dp[m][a][b]表示处理完前m对后，第m栋房屋颜色为a、第n-m+1栋房屋颜色为b的合法方案数（其中a、b为0/1/2代表三种颜色）。

初始状态 #

处理第1对时，仅需满足对称约束（a≠b），无相邻约束。因此：

• 若a≠b，则dp[1][a][b] = 1；
• 若a=b，则dp[1][a][b] = 0。
  初始总方案数为3*2=6，符合预期。

状态转移 #

处理第m+1对时（对应第m+1栋和第n-m栋），需同时满足三个约束：

1. 第m+1栋与前一栋（第m栋）颜色不同：c≠a（c为第m+1栋颜色）；
2. 第n-m栋与前一栋（第n-m+1栋）颜色不同：d≠b（d为第n-m栋颜色）；
3. 第m+1栋与对称的第n-m栋颜色不同：c≠d。

对所有满足条件的(a,b)，将dp[m][a][b]累加至dp[m+1][c][d]，每一步操作对1e5取模。

最终结果 #

当处理完最后一对（m = n/2）时，第n/2栋与第n/2+1栋是相邻的，因此需额外满足a≠b（即最后一对的两个房屋颜色不同）。最终答案为所有满足a≠b的dp[n/2][a][b]之和，再对1e5取模。

优化方向 #

由于颜色只有3种，状态总数仅为3*3=9，可将状态转移转化为矩阵乘法，使用矩阵快速幂将时间复杂度从O(n)优化至O(logn)，适合处理极大的n值。

其他思路补充 #

你提到的“从两端向中间递归”的思路本质和上述DP一致，核心都是逐对处理对称组，避免循环依赖。而容斥原理因补集的交集难以计算，实际操作中可行性较低。

内容的提问来源于stack exchange，提问作者duckrabbit