题目大意 有个2行n列的网格，c种颜色。 有些格子的颜色是固定的。 不能把相邻的格子染成同色，问剩下的格子的染色方案数模(10^9+9)。(n,cleq 10^5;) 题解 “相邻不同色”让人想到可以把染完色的段的两个右（左）端点染上的颜色记在状态里进行dp。 发现对于一段连续的没有颜色固定的格的列，它的染色方案只与它的长度和它前后两端的已染色的格的相同情...