K. King’s Palace

折半枚举。分成长度为\(k\)和\(n-k\)的两部分。

先预处理，\(3^k\)枚举左边的每种染色方案。对每一个合法方案都算一个二进制mask1，mask1表示该染色方案对右边的颜色限制，一共\(2^{3(n-k)}\)种。最后可以统计出每一个mask1对应多少种左边的染色方案。

然后\(3^{(n-k)}\)枚举右边的染色方案，对每个方案也算一个二进制mask2，mask2表示染色方案中哪些颜色被选了。只需要统计有多少mask1满足mask2&mask1=0即可。在mask1上进行子集DP预处理后，对于每一个mask2，可实现\(O(1)\)查询答案。

总复杂度 \(O(3(n-k)2^{3(n-k)}+3^k+3^{(n-k)})\)。取\(k=15\)即可通过。