这是一个创建于 2017 天前的主题，其中的信息可能已经有所发展或是发生改变。
第一感觉是 DP，但是深入思考之后发现前 K 列可能并不符合同行和同列的颜色不完全相同，但是加上一列可以使得整个 K+1 列变成符合要求的 pattern。这种情况下，简单的 DP 的状态是无法表示这种情况的。想了几种状态的表示，比如分成前 k 列有 j 行是颜色完全相同的，但是感觉都不太正确。不知道这题应该从哪个方面入手。
28 条回复 • 2019-05-20 12:11:25 +08:00
 |
1
zycpp 2019-05-17 17:04:35 +08:00 via iPhone  1
机试还是面试
|
 |
2
wfgu 2019-05-17 17:14:45 +08:00 via Android 1
写状态转移矩阵，然后矩阵幂吧。感觉
|
 |
3
HuHui 2019-05-17 17:18:58 +08:00
阿里？
|
 |
4
wutiantong 2019-05-17 17:20:22 +08:00
174 这个结果能快速求出么？
|
 |
5
letianqiu OP |
|
6
wutiantong 2019-05-17 17:33:00 +08:00
@letianqiu 所以你觉得 174 这个数字是怎么来的呢？是直接数出来的，还是有办法推算出来？
|
 |
7
rrfeng 2019-05-17 17:38:24 +08:00
我好奇这种题来个数学家直接写公式（假如有通项公式的话）能算过吗？
|
|
8
wutiantong 2019-05-17 17:40:19 +08:00
@rrfeng 只要正确，当然算过了，而且很 nice 啊
|
 |
9
lance6716 2019-05-17 17:42:26 +08:00 via Android
记录最近三行的状态就行了啊
|
 |
10
LucKkK 2019-05-17 17:45:23 +08:00
是我膨胀了 居然还敢看一下题目
|
|
11
wutiantong 2019-05-17 17:56:36 +08:00
174 = 6*6*6 - ( 2*3*8 - 6 )
|
 |
12
Justin13 2019-05-17 18:06:33 +08:00 via Android
感觉是排列组合的问题
|
 |
13
linhua 2019-05-17 18:08:51 +08:00
2 个不同的 总共有 A(3,2) = 6 个
不考虑第二点 ： 列可以重复总共有 6*6*6 只有一列重复： 总共有 6*2*2 两列都重复：总共有 6 所有总共有 6*6*6 - 6*2*2 *2(减两次，减多了，再加上后面的 6 ） + 6 |
 |
14
clatisus 2019-05-17 18:10:17 +08:00 via iPhone 1
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)。 |
|
16
wutiantong 2019-05-17 18:21:06 +08:00
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 |
|
17
wutiantong 2019-05-17 18:24:26 +08:00 1
能看懂我写的这些递归式的同学 排列组合一定学得不错。
|
|
18
clatisus 2019-05-17 18:26:53 +08:00 via iPhone
好像还有个更快的做法：
你对行进行容斥，枚举有几行满足行是同色的，然后就只需要对每一列选一个颜色使得列不同色。这里的列是独立的，计算一列的答案之后快速幂 O(log n) 就可以。 所以复杂度是 O(mlog n)，这里 m=3，因为容斥只需要知道有多少行同色，乘上组合数就行，不用枚举 2^m。 |
 |
19
geelaw 2019-05-17 18:37:49 +08:00 via iPhone 1
进行如下计算：
满足第二个条件的 满足第二个条件且第一行全同 满足第二个条件且前两行分别全同 满足第二个条件且前三行分别全同 然后用容斥原理算出需要的答案。 也可以用动态规划来做，用 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。 状态转移方程写起来比较麻烦，略去。 |
 |
20
wpzero 2019-05-18 07:28:57 +08:00 via iPhone
n 等于 2 174 n 等于 3 156
|
 |
21
cjh1095358798 2019-05-18 08:26:09 +08:00
完蛋，不会
|
 |
22
ZeroW 2019-05-18 15:25:44 +08:00 via Android
高中排列组合问题・_・?还是比较难的那种
|
|
23
letianqiu OP @wpzero 你的答案是不正确的
@wutiantong 你的递归结果是错误的。 @geelaw 我不是很明白你这么分组的正确性，比如一行完全相同颜色，这行不一定出现在第一行。我稍微修改了一下你的定义。对于有一行颜色全同的，我分成满足第二个条件且第一行颜色都是 R，满足第二个条件且第一行颜色都是 G，满足第二个条件且第一行都是 B，满足第二个条件且第二行都是 R，。。。一共 9 个集合，然后应用容斥原理，就可以算出答案。 |
|
24
geelaw 2019-05-19 18:12:45 +08:00
@letianqiu #23 各行之间是对称的，答案是 A-3B+3C-D。在计算 B 的时候已经考虑了第一行可以以三种方式全同，在计算 C 的时候已经考虑了前两行可以以 9 种方式分别全同（实际计算需要拆开成 3+6 ），等等。
|
|
26
wutiantong 2019-05-20 09:55:12 +08:00
@letianqiu 因为我 f2()的式子少算了两个系数 2，应该是 f2(n) = f2(n-1) * 8 + t1(n-1) * 2 * 6 + s1(n-1) * 2 * 2 * 5 + 28
我这次验算过了，结果没问题。 |
|
27
wutiantong 2019-05-20 11:37:36 +08:00
还可以给出另一个递推关系：
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 |
|
28
wutiantong 2019-05-20 12:11:25 +08:00 via iPhone
@geelaw 结果还是你的解法最简洁直接啊
|
Select Language