3643.覆色
2026-09-13
题解
容易发现,所有颜色只能出现一个格子或者两个相邻的格子,并且当存在两个格子时,其颜色一定大于两端颜色(假设边界外颜色为 0)。
这就启发我们,每对颜色相同的两个格子一定是一个峰值,而且所有合法方案一定能被涂出来,进而只需要考虑怎么计数。
既然有峰值,有颜色,将其放进状态中,即 f[i][j] 表示 i 种不同颜色都出现凑出 j 个峰值的方案数。
至于转移,将颜色按照从小到大的顺序进行,每次考虑插入位置:
- 插到旧的峰值旁边,峰值数量不变,每个峰值两边的格子都可选(两个峰值不能相邻),所以有 2j 个位置可选,方案数为 2j⋅f[i−1][j]。
- 形成一个新的峰值,总共 i 个空位(注意每种颜色都要出现),去除 2j 个峰值段,加上数列开始和结尾两个位置,也就是 (i−2j+2)⋅f[i−1][j−1]。
那么状态转移方程:
f[i][j]=2j⋅f[i−1][j]+(i−2j+2)⋅f[i−1][j−1]
由于 f[i][j] 只用到了 f[i−1][j] 和 f[i−1][j−1],可以类比 0/1 背包使用倒序枚举转移,优化空间。
考虑答案统计。
假设最终合并后 x 个色段,由于至少要有 m 并且每个颜色最少一个格子最多两个格子,则 1≤x≤min(m,n−1)。
至于选择的颜色,m 必须出现占一个,即 (x−1m−1)。
这 x 个颜色中 n−x 个占居两个位置,假设 y 个峰值必须占两个,其他的任意选,即 (n−x−yx−y)。
最终答案为:
ans=x=1∑min(m,n−1)(x−1m−1)j∑(n−x−yx−y)f[x][j]
由于 m 的上限很大,考虑预处理 n 的阶乘,至于 (x−1m−1) 通过 (x−1m−1)=(x−2m−1)×x−1m−x+1。
做完了。
