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

[letianqiu]

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

[cjh1095358798]

完蛋，不会

[ZeroW]

高中排列组合问题・_・?还是比较难的那种

[letianqiu]

@wpzero 你的答案是不正确的
@wutiantong 你的递归结果是错误的。
@geelaw 我不是很明白你这么分组的正确性，比如一行完全相同颜色，这行不一定出现在第一行。我稍微修改了一下你的定义。对于有一行颜色全同的，我分成满足第二个条件且第一行颜色都是 R，满足第二个条件且第一行颜色都是 G，满足第二个条件且第一行都是 B，满足第二个条件且第二行都是 R，。。。一共 9 个集合，然后应用容斥原理，就可以算出答案。

[geelaw]

@letianqiu #23 各行之间是对称的，答案是 A-3B+3C-D。在计算 B 的时候已经考虑了第一行可以以三种方式全同，在计算 C 的时候已经考虑了前两行可以以 9 种方式分别全同（实际计算需要拆开成 3+6 ），等等。

[letianqiu]

@geelaw 懂了，我实际上就是把所有的可能具体列出来，你则是把对称的归到一起了。

[wutiantong]

@letianqiu 因为我 f2()的式子少算了两个系数 2，应该是 f2(n) = f2(n-1) * 8 + t1(n-1) * 2 * 6 + s1(n-1) * 2 * 2 * 5 + 28
我这次验算过了，结果没问题。

[wutiantong]

还可以给出另一个递推关系：

p3(2) = 24*23 - 9*8*7 + (18*6+9*2) = 174
p3(3) = 24*23*22 - 9*8*7*6 + 18*6 = 9228
p3(4) = 24*23*22*21 - 9*8*7*6*5
...
p3(n) = 24!/(24-n)! - 9!/(8-n)!
...
p3(8) = 24!/16! - 9!
p3(9) = 24!/15!
...
p3(24) = 24!
p3(25) = 0
...

结果为：
f3(n) = p3(n) + p3(n-1) * G(n, n-1) + p3(n-2) * G(n, n-2) + ... + p3(2) * G(n, 2)

其中：
G(n, i) = G(n-1, i) * i + G(n-1, i-1)
G(n, n) = 1
G(n, 1) = 1

[wutiantong]

@geelaw 结果还是你的解法最简洁直接啊