今天的一道面试题没能写出来，求思路。

[letianqiu]

第一感觉是 DP，但是深入思考之后发现前 K 列可能并不符合同行和同列的颜色不完全相同，但是加上一列可以使得整个 K+1 列变成符合要求的 pattern。这种情况下，简单的 DP 的状态是无法表示这种情况的。想了几种状态的表示，比如分成前 k 列有 j 行是颜色完全相同的，但是感觉都不太正确。不知道这题应该从哪个方面入手。

[zycpp]

机试还是面试

[wfgu]

写状态转移矩阵，然后矩阵幂吧。感觉

[HuHui]

阿里？

[wutiantong]

174 这个结果能快速求出么？

[letianqiu]

@wutiantong 174 感觉上是作为 base case 的。
@HuHui 不是
@zycpp 机试

[wutiantong]

@letianqiu 所以你觉得 174 这个数字是怎么来的呢？是直接数出来的，还是有办法推算出来？

[rrfeng]

我好奇这种题来个数学家直接写公式（假如有通项公式的话）能算过吗？

[wutiantong]

@rrfeng 只要正确，当然算过了，而且很 nice 啊

[lance6716]

记录最近三行的状态就行了啊

[LucKkK]

是我膨胀了 居然还敢看一下题目

[wutiantong]

174 = 6*6*6 - ( 2*3*8 - 6 )

[Justin13]

感觉是排列组合的问题

[linhua]

2 个不同的 总共有 A(3,2) = 6 个

不考虑第二点 ： 列可以重复总共有 6*6*6
只有一列重复： 总共有 6*2*2
两列都重复：总共有 6

所有总共有 6*6*6 - 6*2*2 *2(减两次，减多了，再加上后面的 6 ） + 6

[clatisus]

dp[i][j][k] (i,j,k\in {0,1,2,3})。每一行记录四种状态：全红、全蓝、全绿、已经至少有两种颜色。

转移的时候枚举这一列的颜色，有 24 种（去掉全色）。

这道题 n 不大，直接转移的话复杂度是 O(4^3*24*n)。矩阵乘法优化的话就是 O((4^3)^3*log n)。

[clatisus]

@HuHui 阿里笔试界面…一言难尽的丑 而且还有摄像头验证保证你没有办法低头打草稿

[wutiantong]

if n > 2; f3(n) = f3(n-1) *24 + f2(n-1) * 3 * 3 * 16 + t1(n-1) * 3 * 3 * 10 + s1(n-1) * 3 * 6 * 11 + 174
f3(2) = 174

if n > 2; f2(n) = f2(n-1) * 8 + t1(n-1) * 6 + s1(n-1) * 2 * 5 + 28
f2(2) = 28

if n >=2; t1(n) = 2^n - 2
if n >= 2; s1(n) = 3^n - 3

[wutiantong]

能看懂我写的这些递归式的同学 排列组合一定学得不错。

[clatisus]

好像还有个更快的做法：

你对行进行容斥，枚举有几行满足行是同色的，然后就只需要对每一列选一个颜色使得列不同色。这里的列是独立的，计算一列的答案之后快速幂 O(log n) 就可以。

所以复杂度是 O(mlog n)，这里 m=3，因为容斥只需要知道有多少行同色，乘上组合数就行，不用枚举 2^m。

[geelaw]

进行如下计算：
满足第二个条件的
满足第二个条件且第一行全同
满足第二个条件且前两行分别全同
满足第二个条件且前三行分别全同

然后用容斥原理算出需要的答案。

也可以用动态规划来做，用 f(0/1/2/3,0/1/2/3,0/1/2/3,k) 表示如下状态的染色方法数：
前三个参数表示第一二三行是否已经有两个颜色，是则是 0，否则不是 0 且等于全同的颜色；
第三个参数表示一共有多少列。

初始状态是 f(x,y,z,1)=0 若 xyz=0，否则等于 1。
状态转移方程写起来比较麻烦，略去。

[wpzero]

n 等于 2 174 n 等于 3 156