题意理解

我们有一个 $2 \times n$ 的网格，每个格子可以染 $c$ 种颜色之一，但相邻格子（上下左右）不能同色。
一些格子已经固定了颜色（非零值），其他格子（值为 $0$）需要染色。
求合法染色方案数，对 $10^9+9$ 取模。

核心难点

1. 相邻约束复杂：每个格子与最多 4 个格子相邻，但网格只有两行，所以主要约束是：

   • 上下相邻（同一列的两个格子不能同色）
   • 左右相邻（同行相邻列不能同色）

2. 已染色格子的固定：已染色格子会限制周围格子的选择。

3. n 和 c 很大：$n$ 最多 $10^5$，$c$ 最多 $10^5$，需要高效 DP 或递推。

解题思路

状态定义

因为只有两行，我们可以按列 DP。
设 $dp[i][a][b]$ 表示前 $i$ 列，且第 $i$ 列上下格子颜色分别为 $a$ 和 $b$ 的方案数。
但这样状态数是 $O(n \cdot c^2)$，太大，需要优化。

关键观察

对于相邻两列，只有四种颜色关系（设第 $i$ 列颜色为 $(a,b)$，第 $i+1$ 列颜色为 $(c,d)$）：

1. $a \neq b, a \neq c, b \neq d, c \neq d$，且 $a \neq d, b \neq c$ 不要求（因为不同列上下不相邻）。 实际上约束是：

   • 上下不同：$a \neq b$，$c \neq d$
   • 左右同行不同：$a \neq c$，$b \neq d$

2. 当 $a,b,c,d$ 互不相同时，方案数容易计算；当有相同时需要分类讨论。

状态简化

由于对称性，可以把一列的颜色情况分为几类：

• S1：两格颜色相同（但这种情况在上下相邻时不允许，除非该列已固定颜色且相同，但题目一般不允许这样，因为相邻不能同色，所以这种情况通常不存在，除非固定颜色冲突直接答案为 0）。 实际上，初始时上下不能同色，所以 $a \neq b$。

• S2：两格颜色不同。

对于不同列之间的转移，我们关心的是相邻列的颜色交集情况。

经典做法：用相同颜色对的数量来划分状态

设：

• $f[i]$：前 $i$ 列合法染色，且第 $i$ 列的上下两个格子颜色不同，并且第 $i$ 列与第 $i-1$ 列的颜色集合没有相同颜色（即完全不同）的方案数。
• $g[i]$：前 $i$ 列合法染色，且第 $i$ 列的上下两个格子颜色不同，并且第 $i$ 列与第 $i-1$ 列的颜色集合恰有 1 个相同颜色的方案数。

注意：不可能有两个相同颜色，因为如果上下都相同，就与“上下不同色”矛盾。

转移方程

假设第 $i$ 列与第 $i-1$ 列的颜色集合完全不同（即 $f[i]$ 状态）：

• 对于第 $i+1$ 列与第 $i$ 列完全不同：
  第 $i$ 列用了 2 种颜色，第 $i+1$ 列要从剩下的 $c-2$ 种颜色中选 2 种，且上下排列有 2 种方式（交换上下），但要满足与第 $i$ 列左右不同：
  实际上，第 $i+1$ 列的两种颜色不能与第 $i$ 列对应上下相同，所以选择方式为 $(c-2)(c-3)$（选两种不同颜色，且与第 $i$ 列两个颜色都不同）。
  所以转移：$f[i+1] += f[i] \times (c-2) \times (c-3)$

• 对于第 $i+1$ 列与第 $i$ 列恰有一个相同颜色：
  相同颜色可以在上行或下行，有两种情况。
  假设相同颜色在上行：那么第 $i+1$ 列上行颜色固定（与第 $i$ 列上行相同），下行不能与上行相同，也不能与第 $i$ 列下行相同，所以有 $c-2$ 种选择。
  同理相同颜色在下行：也有 $c-2$ 种选择。
  所以转移：$g[i+1] += f[i] \times 2 \times (c-2)$

假设第 $i$ 列与第 $i-1$ 列恰有一个相同颜色（即 $g[i]$ 状态）：

设第 $i$ 列颜色为 $(x,y)$，第 $i-1$ 列颜色为 $(x,z)$（相同在上行）或 $(z,y)$（相同在下行），以第一种为例：

• 对于第 $i+1$ 列与第 $i$ 列完全不同：
  第 $i+1$ 列两个颜色要与 $(x,y)$ 都不同，且上下不同。
  选择方式：从 $c-2$ 种颜色中选 2 种，且排列方式 2 种，但要排除与第 $i$ 列左右相同的情况，实际上方案数为 $(c-2)(c-3)$（与上面类似）。
  所以 $f[i+1] += g[i] \times (c-2) \times (c-3)$

• 对于第 $i+1$ 列与第 $i$ 列恰有一个相同颜色：
  情况稍复杂，但可以推导出方案数为 $(c-2) + (c-3) = 2c-5$（分相同颜色在哪个位置，以及另一种颜色的选择限制）。
  所以 $g[i+1] += g[i] \times (2c-5)$

初始化和已染色处理

1. 如果第一列两个格子都未染色：
   $f[1] = c(c-1)$（任选两种不同颜色，上下可交换），$g[1] = 0$（因为不存在前一列）。

2. 如果第一列有已染色格子：
   根据固定颜色确定初始状态。

3. 对于已染色列：
   在转移时，只能选择符合固定颜色的状态。
   如果一列中两个格子都固定了颜色，就直接检查是否合法（上下不同，左右与相邻列不同）。
   如果只有一个格子固定，另一个格子从剩余颜色中选择。

整体方案

把网格按列处理，相邻两列之间用 $f$ 和 $g$ 状态转移。
遇到已染色格子时，只保留符合颜色的状态。
最终答案是最后一列的 $f[n] + g[n]$（因为最后一列与前一列的关系不影响总数，但我们的状态是到第 n 列且满足规则的方案数，需要根据初始化调整）。

关键代码框架（伪代码）

MOD = 1e9+9;
f[0] = 1, g[0] = 0; // 根据第1列实际情况初始化
for i = 1 to n-1:
    nf = 0, ng = 0;
    if 第i列和第i+1列没有固定颜色冲突:
        nf += f[i-1] * (c-2) * (c-3) % MOD;
        ng += f[i-1] * (2*(c-2)) % MOD;
        nf += g[i-1] * (c-2) * (c-3) % MOD;
        ng += g[i-1] * (2*c-5) % MOD;
    // 如果有固定颜色，要调整转移系数
    f[i] = nf, g[i] = ng;
ans = (f[n-1] + g[n-1]) % MOD;

总结

这道题的核心是发现相邻列颜色关系只有两种模式，并用 $f$ 和 $g$ 表示，将复杂度降到 $O(n)$。
已染色点处理时，只需在转移时限制颜色选择即可。
推导转移系数需要仔细讨论颜色不重复的条件。