子任务 5：用第二次筛选处理双固定列（通过子任务 1–6，共 80 分）

双固定列不需要增加状态维数

子任务 5 满足 $n,m\le10^4$，第一列和最后一列都有预置士兵，但同一列现在可能有两个预置士兵。仍把至少有一个预置士兵的列称为关键列，依次位于 $\ell_1<\cdots<\ell_k$。

每个关键列选一个预置格作为固定端：有上格时选上格，否则选下格。其所在行为 $s_j\in\{0,1\}$，兵种为 $p_j$。另一个格子的预置兵种记为 $b_j$，没有预置时令 $b_j=0$。设 $f(j,c)$ 为填好前 $\ell_j$ 列、满足这些列全部预置条件、且当前关键列另一格兵种恰好为 $c$ 的方案数。

当两格都已固定时，只需在这张一维表里保留 $c=b_j$，而不是再增加一维枚举固定的兵种。因此可以先解决“给定右端一格”的转移，再用另一个预置格进行筛选。

空白段中保留什么信息

考虑从第 $j$ 个关键列到第 $j+1$ 个关键列，令 $d=\ell_{j+1}-\ell_j$，右端固定端的行为 $s'$、兵种为 $q$。在本段始终以行 $s'$ 为第一个兵种坐标，另一行为第二个坐标。

设 $F(t,x,y)$ 表示填好前 $\ell_j+t$ 列、当前两坐标兵种恰好为 $x,y$ 的方案数，$0\le t\le d$。左端及以前的预置条件已施加，右端的两个预置条件都暂不施加。对于同列相同的兵种，规定 $F(t,x,x)=0$。

定义

$$\begin{aligned} S(t)&=\sum_{x=1}^{m}\sum_{y=1}^{m}F(t,x,y),\\ R(t,c)&=\sum_{y=1}^{m}F(t,c,y),\qquad C(t,c)=\sum_{x=1}^{m}F(t,x,c),\\ H(t,c)&=F(t,q,c). \end{aligned}$$

$H$ 是目标兵种对应的一行状态，称为目标截面；它不是全部方案的分布。中间列的第一个坐标可以取任意兵种，转移依靠 $S,R,C$ 保留这些方案的信息。

新列两兵种 $x\ne y$ 分别需要避开同一物理行的前驱兵种，容斥得到

$$F(t+1,x,y)=S(t)-R(t,x)-C(t,y)+F(t,x,y).$$

对所有 $y\ne x$ 求和，其中 $\sum_{y\ne x}C(t,y)=S(t)-C(t,x)$，于是

$$\begin{aligned} R(t+1,x) &=(m-1)(S(t)-R(t,x))-(S(t)-C(t,x))+R(t,x)\\ &=(m-2)(S(t)-R(t,x))+C(t,x). \end{aligned}$$

对称地，

$$C(t+1,c)=(m-2)(S(t)-C(t,c))+R(t,c).$$

每个合法旧列扩展一列空白时，两格分别避开旧兵种有 $(m-1)^2$ 种，再去掉两格同色的 $m-2$ 种，故记

$$D=m^2-3m+3,$$

则 $S(t+1)=D\,S(t)$。截面直接满足

$$H(t+1,c)= \begin{cases} S(t)-R(t,q)-C(t,c)+H(t,c),&c\ne q,\\ 0,&c=q. \end{cases}$$

所有方程对 $10^9+9$ 取模，负数归一化。到达右端以前，不应对 $H$ 之外的全部状态施加兵种 $q$，否则会把整段误当作每列都预置了 $q$。

左端的两种方向与右端的第二次筛选

设左端固定兵种为 $p$、行为 $s$，$f(c)=f(j,c)$，$w=\sum_c f(c)$。使用指示值 $[E]$。

若 $s=s'$，左端状态只有 $x=p$ 的一行非零，因此

$$S(0)=w,\quad R(0,c)=[c=p]w,\quad C(0,c)=f(c),\quad H(0,c)=[p=q]f(c).$$

若 $s\ne s'$，左端固定兵种位于第二个坐标，$F(0,x,y)=[y=p]f(x)$，因此

$$S(0)=w,\quad R(0,c)=f(c),\quad C(0,c)=[c=p]w,\quad H(0,c)=[c=p]f(q).$$

即使左端两格都固定，以上公式仍然成立，因为此时 $f$ 本来就至多有一个非零项，无须新增分支。

递推到 $t=d$ 后，先以 $H(d,c)$ 保证右端固定端的兵种是 $q$。右端另一格预置兵种为 $b_{j+1}$ 时，再令

$$f(j+1,c)= \begin{cases} H(d,c),&b_{j+1}=0\text{ 或 }c=b_{j+1},\\ 0,&\text{其他情况}. \end{cases}$$

若右端两个预置兵种相同，即 $b_{j+1}=q$，唯一可能保留的 $H(d,q)$ 本来就是零，因而自然得到无解。不能把双固定列直接当成“贡献乘一”：它还会限制和左侧相邻格的兵种关系。

例如 $m=5$，左列上下固定为 $(1,2)$，右列上格固定为 $3$。施加右下格条件前，下格取 $1,4,5$ 各有一种方案；取 $2$ 与左下格相同，取 $3$ 与右上格相同，都为零。若右下格再固定为 $4$，保留的方案数为 $1$；固定为 $2$ 或 $3$ 时，答案为 $0$。第二次筛选保留的是计算出的对应项，而不是一个无条件的常数。

下一段必须从筛选后的 $f$ 重算总和与行列和。实现中本段最后一步只计算截面，不计算随后会被重新初始化的其他统计量。

初始化、两端空白与答案

对子任务 5，第一列即关键列。记其固定端兵种为 $p_1$，另一格预置为 $b_1$，初始条件为

$$f(1,c)=[c\ne p_1]\,[b_1=0\text{ 或 }c=b_1].$$

最后一列也是关键列，答案为 $\sum_{c=1}^{m}f(k,c)$。特别是 $n=1$ 时，这个初值已经包含同列冲突检查，直接求和即可。

代码保留一个自然的边界推广：若最左关键列不在第一列，则初值额外乘 $D^{\ell_1-1}$；若最右关键列不在最后一列，则最终答案乘 $D^{n-\ell_k}$。这是因为指定任一合法端点列后，向外增加一列空白总有 $D$ 种扩展，与具体兵种无关。完全没有关键列时，答案为 $m(m-1)D^{n-1}$。线性预处理 $D$ 的各次幂即可。

这一边界推广使代码也适用于子任务 1、2、6：这些组不保证首尾非空，但 $n,m$ 仍不超过 $10^4$。连同对子任务 3、4 的包含关系，本实现自然覆盖子任务 1 至 6；第 7 组的最坏时间开销仍过大。

完整列状态的容斥转移正确检查全部相邻边；封闭统计量只是精确地求和或取截面；右端的两次筛选分别施加两个格子的预置条件。每段之后得到的都是完整的关键列分布，由此归纳可知最终计数正确。

复杂度

时间复杂度为 $O(nm)$。各段逐列推进的距离总和不超过 $n-1$，每步扫描全部兵种；关键列方向切换和双固定筛选也只需 $O(m)$，共至多 $n$ 次。幂表预处理为 $O(n)$。

空间复杂度为 $O(n+m)$。完整保存各处理位置的 $R,C,H$ 最坏需要约 $3nm$ 个整数，在 $n=m=10^4$ 时约为 $1.2$ GB，超过 $512$ MB，故只维护旧、新两层。每次先计算完整新层再交换，固定列分布就是筛选后的截面，不重复保存历史关键列状态。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

int norm(i64 x) {
  return (x % mod + mod) % mod;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i] || b[i]) pos.push_back(i);
  }
  int ways = norm(1LL * m * m - 3LL * m + 3);
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) pw[i] = 1LL * pw[i - 1] * ways % mod;
  if (pos.empty()) {
    cout << 1LL * m * (m - 1) % mod * pw[n - 1] % mod << '\n';
    return;
  }
  int last = pos[0], side = a[last] ? 0 : 1;
  int p = side == 0 ? a[last] : b[last];
  vector<int> dp(m + 1, pw[last]), ndp(m + 1);
  vector<int> row(m + 1), col(m + 1);
  vector<int> next_row(m + 1), next_col(m + 1);
  dp[0] = dp[p] = 0;
  if (a[last] && b[last]) {
    int value = dp[b[last]];
    fill(dp.begin(), dp.end(), 0);
    dp[b[last]] = value;
  }
  for (int j = 1; j < (int)pos.size(); j++) {
    int r = pos[j], next_side = a[r] ? 0 : 1;
    int q = next_side == 0 ? a[r] : b[r];
    int sum = accumulate(dp.begin(), dp.end(), 0LL) % mod;
    fill(row.begin(), row.end(), 0);
    fill(col.begin(), col.end(), 0);
    if (side == next_side) {
      row[p] = sum;
      col = dp;
      if (p != q) fill(dp.begin(), dp.end(), 0);
    } else {
      row = dp;
      col[p] = sum;
      int value = dp[q];
      fill(dp.begin(), dp.end(), 0);
      dp[p] = value;
    }
    for (int i = last + 1; i <= r; i++) {
      i64 base = 1LL * sum - row[q];
      for (int x = 1; x <= m; x++) {
        ndp[x] = x == q ? 0 : norm(base - col[x] + dp[x]);
      }
      if (i < r) {
        for (int x = 1; x <= m; x++) {
          next_row[x] = norm(1LL * (m - 2) * (sum - row[x]) + col[x]);
          next_col[x] = norm(1LL * (m - 2) * (sum - col[x]) + row[x]);
        }
        row.swap(next_row);
        col.swap(next_col);
        sum = 1LL * sum * ways % mod;
      }
      dp.swap(ndp);
    }
    if (a[r] && b[r]) {
      int value = dp[b[r]];
      fill(dp.begin(), dp.end(), 0);
      dp[b[r]] = value;
    }
    last = r;
    side = next_side;
    p = q;
  }
  int ans = accumulate(dp.begin(), dp.end(), 0LL) % mod;
  cout << 1LL * ans * pw[n - 1 - last] % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

压缩空白区间并枚举关键列兵种（通过子任务 1–6，共 80 分）

从逐列状态到关键列

只看最后一列，就能判断下一列新增的相邻关系。设 $F(i,x,y)$ 为前 $i$ 列已经填好、且第 $i$ 列上下兵种分别为 $x,y$ 的方案数，其中 $1\le x,y\le m$。若 $x=y$，或者二者不符合该列已驻扎的士兵，状态为零。第一列每个合法状态均为 $1$，其余列满足

$$F(i,x,y)=\sum_{\substack{1\le u,v\le m\\u\ne x,\ v\ne y}}F(i-1,u,v).$$

旧状态已经保证 $u\ne v$，因此不必在求和中重复检查。记旧层总和为 $S$、第 $x$ 行之和为 $R_x$、第 $y$ 列之和为 $C_y$，容斥得到

$$F(i,x,y)=S-R_x-C_y+F(i-1,x,y).$$

这把一次转移降至常数时间，但每列仍有 $m(m-1)$ 个状态，总成本为 $O(nm^2)$。

问题出在完全空白的列。如果某一列已有至少一个士兵，就选一个已知兵种作为这列的固定端：优先选上格，否则选下格。固定端的位置和兵种已知，只需记录另一格的兵种，共 $m$ 种可能。

把这些列称为关键列，按顺序记位置为 $\ell_1<\cdots<\ell_k$，位置从 $0$ 开始。设 $f(j,c)$ 为填好直到第 $j$ 个关键列、该列固定端取已知兵种、另一格取 $c$ 的方案数。关键列之间的内部列全为空，我们先解决如何一次跨过它们。

用七类关系描述空白区间

固定左端列的上、下兵种为不同的 $A,B$。两个端点列的下标相差 $d$，所以中间有 $d-1$ 列；$d=0$ 表示同一列。

对于一组指定的右端兵种 $(u,v)$，区间方案数只取决于它们与 $A,B$ 的相等关系。原因是：除 $A,B$ 外，其他兵种可整体重命名，重命名给出合法方案的一一对应。

设 $g(d,t)$ 为相应类别中一个指定右端有序对的方案数。它不是这一类所有右端对的总和。七种类别如下，$O,O'$ 表示不等于 $A,B$ 的兵种，最后一类还要求 $O\ne O'$。

$t$	右端上下兵种	同类有序对的数量
$0$	$(A,B)$	$1$
$1$	$(B,A)$
$2$	$(A,O)$	$m-2$
$3$	$(O,A)$
$4$	$(B,O)$
$5$	$(O,B)$
$6$	$(O,O')$	$(m-2)(m-3)$

同列相同兵种非法，故没有其他类别。初始条件为 $g(0,0)=1$，其余 $g(0,t)=0$。

预处理下一距离时，仍使用上一节的容斥。为简洁，下面的 $h_t$ 表示 $g(d-1,t)$。旧层总和是

$$S=h_0+h_1+(m-2)(h_2+h_3+h_4+h_5)+(m-2)(m-3)h_6.$$

对某个指定兵种求行和、列和，有

$$\begin{aligned} R_A&=h_0+(m-2)h_2,& C_A&=h_1+(m-2)h_3,\\ R_B&=h_1+(m-2)h_4,& C_B&=h_0+(m-2)h_5,\\ R_O&=h_3+h_5+(m-3)h_6,& C_O&=h_2+h_4+(m-3)h_6. \end{aligned}$$

例如，上格已经是指定的 $O$，下格可以为 $A$、$B$，或者除 $A,B,O$ 外的 $m-3$ 种兵种。这里再次体现了“一个指定有序对”与“整类总和”的区别。

若类别 $t$ 的右端对为 $(u,v)$，则

$$g(d,t)=S-R_u-C_v+h_t\pmod P,\qquad P=10^9+9.$$

对每个 $d=1,\ldots,n-1$ 计算七个值，预处理为线性时间。于是，对于具体端点 $(x,y)$、$(u,v)$，比较兵种相等关系即可在常数时间取得区间权重 $K_d(x,y;u,v)$；任一端点两兵种相同，权重为零。

关键列之间的求和为什么能变成一次函数

考虑相邻两个关键列，旧固定兵种为 $p$，新固定兵种为 $q$。旧另一格的兵种记为 $y$，新另一格记为 $z$。设 $W(y,z)$ 为按两列实际上下位置排列端点后得到的 $K_d$。若固定端从上格变成下格，要交换对应端点对的顺序，不能只比较两个固定兵种。

令 $f(y)=f(j-1,y)$，则尚未筛选新列另一格的预置限制时，完整转移为

$$\widetilde f(j,z)=\sum_{y=1}^{m}f(y)W(y,z).$$

旧列已经保证 $f(p)=0$，新列必须令 $\widetilde f(j,q)=0$。

先考虑普通兵种 $z\notin\{p,q\}$。在所有有贡献的 $y$ 中，只须区分：$y=q$、$y=z$、以及其余兵种。对最后一类，端点相等关系完全一致，所以权重相同。

选一个不属于 $\{p,q,z\}$ 的代表 $w$。题目保证 $m\ge5$，这样的代表总能找到。令

$$S=\sum_y f(y),\qquad V=f(q),\qquad H=W(w,z).$$

则

$$\begin{aligned} \widetilde f(j,z) &=V W(q,z)+f(z)W(z,z)+(S-V-f(z))H\\ &=\alpha f(z)+\beta,\\ \alpha&=W(z,z)-H,\\ \beta&=S H+V\bigl(W(q,z)-H\bigr). \end{aligned}$$

对于所有普通 $z$，三个权重所代表的相等关系都相同，因此 $\alpha,\beta$ 也相同。只取一个普通代表就能计算这两个系数。若 $p=q$，则 $V=0$，相关退化项自然消失。

剩下的新兵种 $z=p$ 需要单独计算。当 $p\ne q$ 时，旧 $y$ 只分为 $q$ 和其余有效兵种：

$$\widetilde f(j,p)=V W(q,p)+(S-V)W(w,p).$$

当 $p=q$ 时该值就是零。因此每次关键列转移只需：对所有兵种统一做 $x\mapsto\alpha x+\beta$，再修正兵种 $p$ 和 $q$ 两处。

例如 $m=5$，两列的上格分别固定为 $1,2$，下格未定。第一列的状态为 $f(1)=0$，其余为 $1$，故 $S=4$。对于新下格 $z=3,4,5$，旧下格只须排除 $z$，得到 $\widetilde f(j,z)=4-f(z)=3$；新下格取 $1$ 时，旧下格原本就不能取 $1$，故有 $4$ 种；取 $2$ 时非法。答案为 $4+3+3+3=13$。这展示了统一更新和两个例外分别承担的作用。

若新列上下两格都已固定，仍按上述方式转移，随后只保留另一格的指定兵种，其他状态全部清零。若上下固定兵种相同，被保留的值本来就是零。

显式保存每个关键列的状态

对子任务 1 到 6，$n,m$ 都不超过 $10^4$。可以保存完整的 $f(j,c)$：每一步先遍历旧层求 $S$，再对所有 $c$ 显式执行一次函数，修正两个特殊兵种，最后应用双固定列筛选。这里完全使用上一节的方程，只是不进一步优化全体状态的修改。

当固定兵种或固定端的上下位置改变时，重新根据端点关系查询权重。某个乘数为零时，显式赋值仍然正确，也不需要求逆元或额外分类。

两端空白列与最终答案

设某一列已指定不同的上下兵种。与它相邻的一列全部空白时，上下兵种需要分别避开它们，并且彼此不同。先分别选择得到 $(m-1)^2$ 种，其中两格相同且不等于原来两种兵种的情况有 $m-2$ 种，所以扩展数为

$$D=(m-1)^2-(m-2)=m^2-3m+3.$$

这个数与指定的具体兵种无关。因此，最左关键列在位置 $\ell_1$ 时，初始状态为

$$f(1,c)= \begin{cases} D^{\ell_1},&c\ne p_1\text{ 且符合该列另一格的预置限制},\\ 0,&\text{其他情况}. \end{cases}$$

依次转移所有关键列后，右边剩余 $n-1-\ell_k$ 列也逐列贡献 $D$，答案为

$$\left(\sum_{c=1}^{m}f(k,c)\right)D^{n-1-\ell_k}\pmod P.$$

若完全没有关键列，第一列有 $m(m-1)$ 种选择，其余每列贡献 $D$，答案直接为 $m(m-1)D^{n-1}$。$n=1$ 时上述公式也成立。预先保存 $D^0,\ldots,D^n$ 即可。

逐列容斥保证了区间权重的正确性，七类合并来自兵种重命名的一一对应，关键列递推枚举了全部端点兵种且没有重复。显式逐兵种更新严格执行该递推；再结合两端的独立扩展，覆盖了完整网格的所有合法方案。

复杂度

时间复杂度为 $O(n+km)$：七类空段权重和幂表用 $O(n)$ 预处理，每个关键列统计并填写 $m$ 个状态。空间复杂度为 $O(n+km)$，完整保留关键列状态；$k,m\le10^4$ 时约有 $10^8$ 个整数，约 400 MB，连同输入和辅助表可放入题目的 512 MB。

该方法不依赖“只在第一行预置”“每列至多一个预置”或“首尾列有预置”，所以自然覆盖子任务 1 至 6。第 7 组的完整状态可能需要约 40 GB，时间成本也会随 $km$ 增长。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

int norm(i64 x) {
  return (x % mod + mod) % mod;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i] || b[i]) pos.push_back(i);
  }
  const int ways = norm(1LL * m * m - 3LL * m + 3);
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) pw[i] = 1LL * pw[i - 1] * ways % mod;
  if (pos.empty()) {
    cout << 1LL * m * (m - 1) % mod * pw[n - 1] % mod << '\n';
    return;
  }
  // Relative to fixed left colors A,B: AB,BA,AO,OA,BO,OB,OO'.
  const vector<pair<int, int>> type = {{0, 1}, {1, 0}, {0, 2}, {2, 0}, {1, 2}, {2, 1}, {2, 2}};
  vector<array<int, 7>> dp_gap(n);
  dp_gap[0][0] = 1;
  for (int d = 1; d < n; d++) {
    const auto& pre = dp_gap[d - 1];
    i64 sum = norm(pre[0] + 1LL * pre[1] + 1LL * (m - 2) * (0LL + pre[2] + pre[3] + pre[4] + pre[5])
                  + 1LL * (m - 2) * (m - 3) % mod * pre[6]);
    vector<int> row = {norm(pre[0] + 1LL * (m - 2) * pre[2]),
                      norm(pre[1] + 1LL * (m - 2) * pre[4]),
                      norm(pre[3] + 1LL * pre[5] + 1LL * (m - 3) * pre[6])};
    vector<int> col = {norm(pre[1] + 1LL * (m - 2) * pre[3]),
                      norm(pre[0] + 1LL * (m - 2) * pre[5]),
                      norm(pre[2] + 1LL * pre[4] + 1LL * (m - 3) * pre[6])};
    for (int t = 0; t < 7; t++) {
      auto [x, y] = type[t];
      dp_gap[d][t] = norm(sum - row[x] - col[y] + pre[t]);
    }
  }
  auto kernel = [&](int d, int x, int y, int u, int v) {
    if (x == y || u == v) return 0;
    int t;
    if (u == x) t = v == y ? 0 : 2;
    else if (u == y) t = v == x ? 1 : 4;
    else if (v == x) t = 3;
    else if (v == y) t = 5;
    else t = 6;
    return dp_gap[d][t];
  };
  vector<vector<int>> dp(pos.size(), vector<int>(m + 1));
  int last = pos[0], side = a[last] ? 0 : 1;
  int p = side == 0 ? a[last] : b[last];
  fill(dp[0].begin() + 1, dp[0].end(), pw[last]);
  dp[0][p] = 0;
  if (a[last] && b[last]) {
    int value = dp[0][b[last]];
    fill(dp[0].begin(), dp[0].end(), 0);
    dp[0][b[last]] = value;
  }
  for (int j = 1; j < (int)pos.size(); j++) {
    int i = pos[j], next_side = a[i] ? 0 : 1;
    int q = next_side == 0 ? a[i] : b[i];
    int d = i - last;
    auto weight = [&](int y, int z) {
      int x = p, u = q;
      if (side) swap(x, y);
      if (next_side) swap(u, z);
      return kernel(d, x, y, u, z);
    };
    int z = 1;
    while (z == p || z == q) z++;
    int w = 1;
    while (w == p || w == q || w == z) w++;
    int sum = accumulate(dp[j - 1].begin(), dp[j - 1].end(), 0LL) % mod;
    int value = dp[j - 1][q];
    int other = weight(w, z);
    int mul = norm(1LL * weight(z, z) - other);
    int add = norm(1LL * sum * other + 1LL * value * (weight(q, z) - other));
    int special = p == q ? 0 : norm(1LL * value * weight(q, p) + 1LL * norm(1LL * sum - value) * weight(w, p));
    for (int x = 1; x <= m; x++) dp[j][x] = (1LL * mul * dp[j - 1][x] + add) % mod;
    dp[j][p] = special;
    dp[j][q] = 0;
    if (a[i] && b[i]) {
      int keep = dp[j][b[i]];
      fill(dp[j].begin(), dp[j].end(), 0);
      dp[j][b[i]] = keep;
    }
    last = i;
    side = next_side;
    p = q;
  }
  int sum = accumulate(dp.back().begin(), dp.back().end(), 0LL) % mod;
  cout << 1LL * sum * pw[n - 1 - last] % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

子任务 4：切换固定行并维护目标截面（通过子任务 3–4，共 40 分）

每列至多一个预置士兵意味着什么

子任务 4 满足 $n,m\le10^4$，每列至多有一个预置士兵，第一列和最后一列都非空。预置士兵可以位于任意一行，因此不能只考虑上格固定的情形。

把非空列按位置记为 $\ell_1<\cdots<\ell_k$。第 $j$ 个关键列的固定兵种为 $p_j$，所在物理行为 $s_j\in\{0,1\}$，另一格未固定。设 $f(j,c)$ 为填好前 $\ell_j$ 列并满足全部预置条件、且该关键列另一格兵种恰好为 $c$ 的方案数，$1\le c\le m$。同列不能同色，所以 $f(j,p_j)=0$。

关键列之间全为空，完整状态需要记录上下两个兵种，但只在右端恢复一个固定兵种对应的截面即可。新增的问题是：相邻关键列的预置士兵可能换行。解决办法不是把输入中的上下行随意互换，而是在处理每一段时，以右端固定兵种所在行为第一个坐标，另一行为第二个坐标。

按右端方向定义列状态

考虑从 $\ell_j$ 到 $\ell_{j+1}$ 的一段，长度差为 $d$，右端兵种为 $q$、所在行为 $s'$。本段的 $F(t,x,y)$ 表示填好前 $\ell_j+t$ 列的方案数，其中行 $s'$ 的兵种为 $x$，另一行的兵种为 $y$。左端及以前的预置条件已经施加，右端条件暂不施加。$F(t,x,x)=0$。

定义总和、行列和与目标截面：

$$\begin{aligned} S(t)&=\sum_{x=1}^{m}\sum_{y=1}^{m}F(t,x,y),\\ R(t,c)&=\sum_{y=1}^{m}F(t,c,y),\qquad C(t,c)=\sum_{x=1}^{m}F(t,x,c),\\ H(t,c)&=F(t,q,c). \end{aligned}$$

这里的矩阵行、列对应兵种坐标，不是网格的物理列。$H$ 只是一份被跟踪的截面，中间列并没有被强制固定为 $q$；转移中的总和必须使用 $S$，不能使用 $\sum_c H(t,c)$。

不管当前选择哪一行为第一个坐标，水平相邻格分别要求第一个坐标不等、第二个坐标不等。因此对 $x\ne y$，完整转移始终是

$$F(t+1,x,y)=S(t)-R(t,x)-C(t,y)+F(t,x,y).$$

这是从全部前驱中减去两类水平冲突，再加回被重复减去的交集。对 $y\ne x$ 求和，得到

$$\begin{aligned} R(t+1,x) &=(m-1)(S(t)-R(t,x))-(S(t)-C(t,x))+R(t,x)\\ &=(m-2)(S(t)-R(t,x))+C(t,x). \end{aligned}$$

由对称性，另有

$$C(t+1,c)=(m-2)(S(t)-C(t,c))+R(t,c).$$

每个合法旧列扩展一列空白的方案数都等于

$$D=(m-1)^2-(m-2)=m^2-3m+3,$$

因为先分别避开左右水平冲突，再排除两格同色的 $m-2$ 种选择。因此 $S(t+1)=D\,S(t)$，并且

$$H(t+1,c)= \begin{cases} S(t)-R(t,q)-C(t,c)+H(t,c),&c\ne q,\\ 0,&c=q. \end{cases}$$

三个长度为 $m$ 的向量和总和构成封闭递推，所有等式在模 $10^9+9$ 下计算。

同行与换行两种初始化

设左端固定兵种为 $p$、所在行为 $s$，左端另一格的分布为 $f(c)=f(j,c)$，令 $w=\sum_c f(c)$。用 $[E]$ 表示命题 $E$ 的指示值。

当 $s=s'$ 时，左端只有第一个坐标 $x=p$ 的状态有效，故

$$S(0)=w,\qquad R(0,c)=[c=p]w,\qquad C(0,c)=f(c),\qquad H(0,c)=[p=q]f(c).$$

当 $s\ne s'$ 时，左端的固定兵种位于第二个坐标，状态矩阵只有第 $p$ 列有效，即 $F(0,x,y)=[y=p]f(x)$。因此

$$S(0)=w,\qquad R(0,c)=f(c),\qquad C(0,c)=[c=p]w,\qquad H(0,c)=[c=p]f(q).$$

两种情况只改变段首初始化，空白列的递推完全相同。特别是换行时，截面不一定全零：它在第二个坐标等于 $p$ 的位置保留 $f(q)$。漏掉这个值，就丢掉了左端未固定格已经取 $q$ 的合法前驱。

例如 $m=5$，左列上格固定为 $1$，右列下格固定为 $2$。按右端方向，以“下、上”为两个坐标。左端有 $w=4$，$R(0,2)=1$，$C(0,1)=4$，而 $H(0,1)=1$。经过一次转移，新上格取 $1$ 时得到 $4-1-4+1=0$；取 $2$ 时同列冲突，仍为零；取 $3,4,5$ 时各有 $4-1=3$ 种，共 $9$ 种。这同时检查了水平冲突和上下坐标的对应。

段末筛选、两端与正确性

递推 $d$ 次后，右端所在行必须取 $q$，直接令

$$f(j+1,c)=H(d,c).$$

下一段根据新的固定行与兵种重新构造 $S,R,C,H$，其中总和重新求 $\sum_c f(j+1,c)$。不施加右端限制时的 $S(d)$ 不能直接传到下一段。代码在每段最后一步仅更新截面，因为此时其余统计量已经不再使用。

首列只有一个预置兵种 $p_1$，所以 $f(1,c)=[c\ne p_1]$；末列也是关键列，答案为 $\sum_c f(k,c)$。$n=1$ 时直接得到 $m-1$。

代码也处理每列至多一个预置、但首尾为空的情形：固定合法端点向空白方向扩展一列总有 $D$ 种选择，故初值乘 $D^{\ell_1-1}$，答案乘 $D^{n-\ell_k}$。全空网格的答案为 $m(m-1)D^{n-1}$。这些幂用线性预处理求出。

交换两个物理行只改变坐标名称，不改变任何相邻关系。两种初始化分别精确表达左端是矩阵中的一行还是一列；封闭递推是完整状态递推的精确投影，段末筛选恰好保留右端预置条件。因此每种合法方案被计入一次，非法方案不被计入。

本方法依赖每列至多一个预置士兵，适用于子任务 3、4；子任务 1、2 虽然规模更小，但没有这一结构保证，不能仅凭规模把它们计入覆盖范围。

复杂度

时间复杂度为 $O(nm)$。空白段及其右端逐列推进，每个位置扫描全部兵种，所有段的距离之和至多为 $n-1$；各关键列的初始化总计 $O(km)$，其中 $k\le n$。

空间复杂度为 $O(n+m)$。完整保存各位置的 $R,C,H$ 最坏约需 $3nm$ 个整数，即约 $1.2$ GB，超过 $512$ MB，所以采用旧、新两层。一次更新先从旧层算出全部新值再交换，右端筛选后的截面同时作为新的关键列分布，不额外保留重复历史。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

int norm(i64 x) {
  return (x % mod + mod) % mod;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i] || b[i]) pos.push_back(i);
  }
  int ways = norm(1LL * m * m - 3LL * m + 3);
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) pw[i] = 1LL * pw[i - 1] * ways % mod;
  if (pos.empty()) {
    cout << 1LL * m * (m - 1) % mod * pw[n - 1] % mod << '\n';
    return;
  }
  int last = pos[0], side = a[last] ? 0 : 1;
  int p = side == 0 ? a[last] : b[last];
  vector<int> dp(m + 1, pw[last]), ndp(m + 1);
  vector<int> row(m + 1), col(m + 1);
  vector<int> next_row(m + 1), next_col(m + 1);
  dp[0] = dp[p] = 0;
  for (int j = 1; j < (int)pos.size(); j++) {
    int r = pos[j], next_side = a[r] ? 0 : 1;
    int q = next_side == 0 ? a[r] : b[r];
    int sum = accumulate(dp.begin(), dp.end(), 0LL) % mod;
    fill(row.begin(), row.end(), 0);
    fill(col.begin(), col.end(), 0);
    if (side == next_side) {
      row[p] = sum;
      col = dp;
      if (p != q) fill(dp.begin(), dp.end(), 0);
    } else {
      row = dp;
      col[p] = sum;
      int value = dp[q];
      fill(dp.begin(), dp.end(), 0);
      dp[p] = value;
    }
    for (int i = last + 1; i <= r; i++) {
      i64 base = 1LL * sum - row[q];
      for (int x = 1; x <= m; x++) {
        ndp[x] = x == q ? 0 : norm(base - col[x] + dp[x]);
      }
      if (i < r) {
        for (int x = 1; x <= m; x++) {
          next_row[x] = norm(1LL * (m - 2) * (sum - row[x]) + col[x]);
          next_col[x] = norm(1LL * (m - 2) * (sum - col[x]) + row[x]);
        }
        row.swap(next_row);
        col.swap(next_col);
        sum = 1LL * sum * ways % mod;
      }
      dp.swap(ndp);
    }
    last = r;
    side = next_side;
    p = q;
  }
  int ans = accumulate(dp.begin(), dp.end(), 0LL) % mod;
  cout << 1LL * ans * pw[n - 1 - last] % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

满分解法（100 分）

从逐列状态到关键列

只看最后一列，就能判断下一列新增的相邻关系。设 $F(i,x,y)$ 为前 $i$ 列已经填好、且第 $i$ 列上下兵种分别为 $x,y$ 的方案数，其中 $1\le x,y\le m$。若 $x=y$，或者二者不符合该列已驻扎的士兵，状态为零。第一列每个合法状态均为 $1$，其余列满足

$$F(i,x,y)=\sum_{\substack{1\le u,v\le m\\u\ne x,\ v\ne y}}F(i-1,u,v).$$

旧状态已经保证 $u\ne v$，因此不必在求和中重复检查。记旧层总和为 $S$、第 $x$ 行之和为 $R_x$、第 $y$ 列之和为 $C_y$，容斥得到

$$F(i,x,y)=S-R_x-C_y+F(i-1,x,y).$$

这把一次转移降至常数时间，但每列仍有 $m(m-1)$ 个状态，总成本为 $O(nm^2)$。

问题出在完全空白的列。如果某一列已有至少一个士兵，就选一个已知兵种作为这列的固定端：优先选上格，否则选下格。固定端的位置和兵种已知，只需记录另一格的兵种，共 $m$ 种可能。

把这些列称为关键列，按顺序记位置为 $\ell_1<\cdots<\ell_k$，位置从 $0$ 开始。设 $f(j,c)$ 为填好直到第 $j$ 个关键列、该列固定端取已知兵种、另一格取 $c$ 的方案数。关键列之间的内部列全为空，我们先解决如何一次跨过它们。

用七类关系描述空白区间

固定左端列的上、下兵种为不同的 $A,B$。两个端点列的下标相差 $d$，所以中间有 $d-1$ 列；$d=0$ 表示同一列。

对于一组指定的右端兵种 $(u,v)$，区间方案数只取决于它们与 $A,B$ 的相等关系。原因是：除 $A,B$ 外，其他兵种可整体重命名，重命名给出合法方案的一一对应。

设 $g(d,t)$ 为相应类别中一个指定右端有序对的方案数。它不是这一类所有右端对的总和。七种类别如下，$O,O'$ 表示不等于 $A,B$ 的兵种，最后一类还要求 $O\ne O'$。

$t$	右端上下兵种	同类有序对的数量
$0$	$(A,B)$	$1$
$1$	$(B,A)$
$2$	$(A,O)$	$m-2$
$3$	$(O,A)$
$4$	$(B,O)$
$5$	$(O,B)$
$6$	$(O,O')$	$(m-2)(m-3)$

同列相同兵种非法，故没有其他类别。初始条件为 $g(0,0)=1$，其余 $g(0,t)=0$。

预处理下一距离时，仍使用上一节的容斥。为简洁，下面的 $h_t$ 表示 $g(d-1,t)$。旧层总和是

$$S=h_0+h_1+(m-2)(h_2+h_3+h_4+h_5)+(m-2)(m-3)h_6.$$

对某个指定兵种求行和、列和，有

$$\begin{aligned} R_A&=h_0+(m-2)h_2,& C_A&=h_1+(m-2)h_3,\\ R_B&=h_1+(m-2)h_4,& C_B&=h_0+(m-2)h_5,\\ R_O&=h_3+h_5+(m-3)h_6,& C_O&=h_2+h_4+(m-3)h_6. \end{aligned}$$

例如，上格已经是指定的 $O$，下格可以为 $A$、$B$，或者除 $A,B,O$ 外的 $m-3$ 种兵种。这里再次体现了“一个指定有序对”与“整类总和”的区别。

若类别 $t$ 的右端对为 $(u,v)$，则

$$g(d,t)=S-R_u-C_v+h_t\pmod P,\qquad P=10^9+9.$$

对每个 $d=1,\ldots,n-1$ 计算七个值，预处理为线性时间。于是，对于具体端点 $(x,y)$、$(u,v)$，比较兵种相等关系即可在常数时间取得区间权重 $K_d(x,y;u,v)$；任一端点两兵种相同，权重为零。

关键列之间的求和为什么能变成一次函数

考虑相邻两个关键列，旧固定兵种为 $p$，新固定兵种为 $q$。旧另一格的兵种记为 $y$，新另一格记为 $z$。设 $W(y,z)$ 为按两列实际上下位置排列端点后得到的 $K_d$。若固定端从上格变成下格，要交换对应端点对的顺序，不能只比较两个固定兵种。

令 $f(y)=f(j-1,y)$，则尚未筛选新列另一格的预置限制时，完整转移为

$$\widetilde f(j,z)=\sum_{y=1}^{m}f(y)W(y,z).$$

旧列已经保证 $f(p)=0$，新列必须令 $\widetilde f(j,q)=0$。

先考虑普通兵种 $z\notin\{p,q\}$。在所有有贡献的 $y$ 中，只须区分：$y=q$、$y=z$、以及其余兵种。对最后一类，端点相等关系完全一致，所以权重相同。

选一个不属于 $\{p,q,z\}$ 的代表 $w$。题目保证 $m\ge5$，这样的代表总能找到。令

$$S=\sum_y f(y),\qquad V=f(q),\qquad H=W(w,z).$$

则

$$\begin{aligned} \widetilde f(j,z) &=V W(q,z)+f(z)W(z,z)+(S-V-f(z))H\\ &=\alpha f(z)+\beta,\\ \alpha&=W(z,z)-H,\\ \beta&=S H+V\bigl(W(q,z)-H\bigr). \end{aligned}$$

对于所有普通 $z$，三个权重所代表的相等关系都相同，因此 $\alpha,\beta$ 也相同。只取一个普通代表就能计算这两个系数。若 $p=q$，则 $V=0$，相关退化项自然消失。

剩下的新兵种 $z=p$ 需要单独计算。当 $p\ne q$ 时，旧 $y$ 只分为 $q$ 和其余有效兵种：

$$\widetilde f(j,p)=V W(q,p)+(S-V)W(w,p).$$

当 $p=q$ 时该值就是零。因此每次关键列转移只需：对所有兵种统一做 $x\mapsto\alpha x+\beta$，再修正兵种 $p$ 和 $q$ 两处。

例如 $m=5$，两列的上格分别固定为 $1,2$，下格未定。第一列的状态为 $f(1)=0$，其余为 $1$，故 $S=4$。对于新下格 $z=3,4,5$，旧下格只须排除 $z$，得到 $\widetilde f(j,z)=4-f(z)=3$；新下格取 $1$ 时，旧下格原本就不能取 $1$，故有 $4$ 种；取 $2$ 时非法。答案为 $4+3+3+3=13$。这展示了统一更新和两个例外分别承担的作用。

若新列上下两格都已固定，仍按上述方式转移，随后只保留另一格的指定兵种，其他状态全部清零。若上下固定兵种相同，被保留的值本来就是零。

延迟执行全体兵种的更新

若每次显式更新 $m$ 个状态，可以得到 $O(n+km)$ 的算法。最大范围下 $k,m$ 都可达 $10^5$，需要进一步避免逐兵种更新。

把当前每个兵种的值表示为

$$f(c)=M r_c+B\pmod P,$$

同时保存总和 $S$。一开始可令所有 $r_c=0$，通过 $B$ 指定统一初值。

当全体状态执行 $x\mapsto\alpha x+\beta$ 且 $\alpha\ne0$ 时，只修改

$$M\leftarrow\alpha M,\qquad B\leftarrow\alpha B+\beta,\qquad S\leftarrow\alpha S+m\beta.$$

由于 $P$ 是质数，非零 $M$ 有逆元。为把一个兵种的值设为 $v$，先查出旧值并修正总和，再写入

$$r_c=(v-B)M^{-1}\pmod P.$$

同时维护 $M^{-1}$；一次非零全体乘法后，它乘上 $\alpha^{P-2}$。快速幂计算该逆元。

不能假设 $\alpha$ 总非零。例如相邻两列的固定端分处不同行时，某些转移的普通状态会全部变成同一个值。当 $\alpha=0$，所有状态应为 $\beta$，此时令 $M=1,B=\beta,S=m\beta$，并把所有旧的 $r_c$ 视为零。

为了不遍历数组清零，为每个兵种保存写入时的版本号，并维护当前版本。全体赋值时增加版本号；查询到旧版本时按 $r_c=0$ 处理。后续单点写入更新其版本。这也直接支持双固定列的“全清零后保留一个值”。

每次转移先读出旧总和、$f(q)$，算好两个普通系数及例外值，再执行更新，避免把新层值误作旧层值。

两端空白列与最终答案

设某一列已指定不同的上下兵种。与它相邻的一列全部空白时，上下兵种需要分别避开它们，并且彼此不同。先分别选择得到 $(m-1)^2$ 种，其中两格相同且不等于原来两种兵种的情况有 $m-2$ 种，所以扩展数为

$$D=(m-1)^2-(m-2)=m^2-3m+3.$$

这个数与指定的具体兵种无关。因此，最左关键列在位置 $\ell_1$ 时，初始状态为

$$f(1,c)= \begin{cases} D^{\ell_1},&c\ne p_1\text{ 且符合该列另一格的预置限制},\\ 0,&\text{其他情况}. \end{cases}$$

依次转移所有关键列后，右边剩余 $n-1-\ell_k$ 列也逐列贡献 $D$，答案为

$$\left(\sum_{c=1}^{m}f(k,c)\right)D^{n-1-\ell_k}\pmod P.$$

若完全没有关键列，第一列有 $m(m-1)$ 种选择，其余每列贡献 $D$，答案直接为 $m(m-1)D^{n-1}$。$n=1$ 时上述公式也成立。预先保存 $D^0,\ldots,D^n$ 即可。

逐列容斥保证了区间权重的正确性，七类合并来自兵种重命名的一一对应，关键列递推枚举了全部端点兵种且没有重复。仿射表示仅改变状态的维护方式，不改变该递推；再结合两端的独立扩展，覆盖了完整网格的所有合法方案。

复杂度

时间复杂度为 $O(n+m+k\log P)$，其中 $k\le n$ 是关键列数量：空段七类和幂表预处理为 $O(n)$，每次关键列转移只有常数次查询、赋值及至多一次模逆元快速幂。

空间复杂度为 $O(n+m)$。保留全部距离的七类状态和输入；关键列完整逻辑表有 $km$ 项，最大约 $40$ GB，超过空间限制，因此只用仿射表示维护当前层，并在更新前保存所需的旧值。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

int norm(i64 x) {
  return (x % mod + mod) % mod;
}

int power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1LL * res * a % mod;
    a = 1LL * a * a % mod;
    b >>= 1;
  }
  return res;
}

// value(x) = mul * raw[x] + add; an old timestamp means raw[x] = 0.
struct Affine {
  int n, epoch = 0, mul = 1, inv = 1, add = 0, sum = 0;
  vector<int> raw, stamp;
  Affine(int n) : n(n), raw(n + 1), stamp(n + 1) {}
  int query(int x) {
    return norm(1LL * mul * (stamp[x] == epoch ? raw[x] : 0) + add);
  }
  void set(int x, int value) {
    sum = norm(1LL * sum - query(x) + value);
    raw[x] = 1LL * norm(1LL * value - add) * inv % mod;
    stamp[x] = epoch;
  }
  void apply(int a, int b) {
    sum = (1LL * a * sum + 1LL * n * b) % mod;
    if (a == 0) {
      epoch++;
      mul = inv = 1;
      add = b;
    } else {
      mul = 1LL * mul * a % mod;
      inv = 1LL * inv * power(a, mod - 2) % mod;
      add = (1LL * a * add + b) % mod;
    }
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i] || b[i]) pos.push_back(i);
  }
  const int ways = norm(1LL * m * m - 3LL * m + 3);
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) pw[i] = 1LL * pw[i - 1] * ways % mod;
  if (pos.empty()) {
    cout << 1LL * m * (m - 1) % mod * pw[n - 1] % mod << '\n';
    return;
  }
  // Relative to fixed left colors A,B: AB,BA,AO,OA,BO,OB,OO'.
  const vector<pair<int, int>> type = {{0, 1}, {1, 0}, {0, 2}, {2, 0}, {1, 2}, {2, 1}, {2, 2}};
  vector<array<int, 7>> dp_gap(n);
  dp_gap[0][0] = 1;
  for (int d = 1; d < n; d++) {
    const auto& pre = dp_gap[d - 1];
    i64 sum = norm(pre[0] + 1LL * pre[1] + 1LL * (m - 2) * (0LL + pre[2] + pre[3] + pre[4] + pre[5])
                  + 1LL * (m - 2) * (m - 3) % mod * pre[6]);
    vector<int> row = {norm(pre[0] + 1LL * (m - 2) * pre[2]),
                      norm(pre[1] + 1LL * (m - 2) * pre[4]),
                      norm(pre[3] + 1LL * pre[5] + 1LL * (m - 3) * pre[6])};
    vector<int> col = {norm(pre[1] + 1LL * (m - 2) * pre[3]),
                      norm(pre[0] + 1LL * (m - 2) * pre[5]),
                      norm(pre[2] + 1LL * pre[4] + 1LL * (m - 3) * pre[6])};
    for (int t = 0; t < 7; t++) {
      auto [x, y] = type[t];
      dp_gap[d][t] = norm(sum - row[x] - col[y] + pre[t]);
    }
  }
  auto kernel = [&](int d, int x, int y, int u, int v) {
    if (x == y || u == v) return 0;
    int t;
    if (u == x) t = v == y ? 0 : 2;
    else if (u == y) t = v == x ? 1 : 4;
    else if (v == x) t = 3;
    else if (v == y) t = 5;
    else t = 6;
    return dp_gap[d][t];
  };
  Affine dp(m);
  int last = pos[0], side = a[last] ? 0 : 1;
  int p = side == 0 ? a[last] : b[last];
  dp.apply(0, pw[last]);
  dp.set(p, 0);
  if (a[last] && b[last]) {
    int value = dp.query(b[last]);
    dp.apply(0, 0);
    dp.set(b[last], value);
  }
  for (int j = 1; j < (int)pos.size(); j++) {
    int i = pos[j], next_side = a[i] ? 0 : 1;
    int q = next_side == 0 ? a[i] : b[i];
    int d = i - last;
    auto weight = [&](int y, int z) {
      int x = p, u = q;
      if (side) swap(x, y);
      if (next_side) swap(u, z);
      return kernel(d, x, y, u, z);
    };
    int z = 1;
    while (z == p || z == q) z++;
    int w = 1;
    while (w == p || w == q || w == z) w++;
    int sum = dp.sum, value = dp.query(q);
    int other = weight(w, z);
    int mul = norm(1LL * weight(z, z) - other);
    int add = norm(1LL * sum * other + 1LL * value * (weight(q, z) - other));
    int special = p == q ? 0 : norm(1LL * value * weight(q, p) + 1LL * norm(1LL * sum - value) * weight(w, p));
    dp.apply(mul, add);
    dp.set(p, special);
    dp.set(q, 0);
    if (a[i] && b[i]) {
      int keep = dp.query(b[i]);
      dp.apply(0, 0);
      dp.set(b[i], keep);
    }
    last = i;
    side = next_side;
    p = q;
  }
  cout << 1LL * dp.sum * pw[n - 1 - last] % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

子任务 3：同一行预置与目标兵种截面（通过子任务 3，共 25 分）

利用第二行没有预置士兵的条件

子任务 3 满足 $n,m\le10^4$，所有预置士兵都在第一行，且第一列、最后一列都有预置士兵。把第一行非空的列称为关键列，位置依次为 $\ell_1<\cdots<\ell_k$。

在关键列处，上格兵种已经确定，只需记录下格兵种。设 $f(j,c)$ 为填好前 $\ell_j$ 列、满足这些列全部预置条件、且第 $\ell_j$ 列下格兵种恰好为 $c$ 的方案数，$1\le c\le m$。若这列上格兵种为 $p$，则 $f(j,p)=0$。

难点是两列之间可能有完全空白的列：经过一列空白后，上格不再固定，不能继续只保存下格的分布。但我们提前知道下一个关键列要求上格等于哪个兵种，因此不必保存全部 $m(m-1)$ 个有序对，只需维护行和、列和，以及那个指定上格兵种对应的一行状态。

从完整列状态推出封闭的统计量

考虑相邻关键列 $\ell_j,\ell_{j+1}$，令 $d=\ell_{j+1}-\ell_j$，右端上格固定兵种为 $q$。在本段内，设 $F(t,x,y)$ 为填好前 $\ell_j+t$ 列、当前列上下兵种恰好为 $x,y$ 的方案数，$0\le t\le d$。它保留左端及以前的预置条件，暂不施加右端的预置条件；同列相同兵种始终非法，即 $F(t,x,x)=0$。

定义

$$S(t)=\sum_{x=1}^{m}\sum_{y=1}^{m}F(t,x,y),\qquad R(t,x)=\sum_{y=1}^{m}F(t,x,y),\qquad C(t,y)=\sum_{x=1}^{m}F(t,x,y).$$

这里的行、列是兵种状态矩阵的行、列，不是网格的物理行、列。再定义目标兵种截面

$$H(t,c)=F(t,q,c),\qquad 1\le c\le m.$$

$H$ 只统计当前上格恰好为 $q$ 的方案，并不意味着中间每列都被强制填成 $q$。中间的全部方案仍由 $S,R,C$ 统计，不能把 $\sum_c H(t,c)$ 当作 $S(t)$。

当下一列暂时不设预置限制时，新上格为 $x$、下格为 $y$，需要分别排除旧上格等于 $x$、旧下格等于 $y$ 的方案。容斥得到，对 $x\ne y$，

$$F(t+1,x,y)=S(t)-R(t,x)-C(t,y)+F(t,x,y).$$

对所有 $y\ne x$ 求和，利用 $\sum_y C(t,y)=S(t)$，得到

$$\begin{aligned} R(t+1,x) &=(m-1)\bigl(S(t)-R(t,x)\bigr) -\bigl(S(t)-C(t,x)\bigr)+R(t,x)\\ &=(m-2)\bigl(S(t)-R(t,x)\bigr)+C(t,x). \end{aligned}$$

上下对称，另一项为

$$C(t+1,c)=(m-2)\bigl(S(t)-C(t,c)\bigr)+R(t,c).$$

对一个已经指定了不同上下兵种的旧列，下一列有 $(m-1)^2$ 种分别避开水平冲突的选择，其中上下相同的非法选择有 $m-2$ 种。记

$$D=(m-1)^2-(m-2)=m^2-3m+3,$$

则 $S(t+1)=D\,S(t)$。目标截面直接使用完整转移：

$$H(t+1,c)= \begin{cases} S(t)-R(t,q)-C(t,c)+H(t,c),&c\ne q,\\ 0,&c=q. \end{cases}$$

这些方程只依赖 $S,R,C,H$ 的上一层，因而三张长度为 $m$ 的表与一个总和已经足够。所有运算均对 $P=10^9+9$ 取模，减法须归一化。

同一行预置时如何开始和结束一段

令左端上格兵种为 $p$，$f(c)=f(j,c)$，$s=\sum_{c=1}^{m}f(c)$。左端状态矩阵只有第 $p$ 行可能非零，因此

$$\begin{aligned} S(0)&=s,\\ R(0,c)&=[c=p]\,s,\\ C(0,c)&=f(c),\\ H(0,c)&=[p=q]\,f(c). \end{aligned}$$

$[E]$ 表示命题 $E$ 成立时为 $1$，否则为 $0$。当 $p\ne q$ 时，目标截面初始全零，但并不代表没有合法方案：经过空白列转移，其他上格兵种的状态仍可进入这个截面。

从 $t=0$ 递推到 $d$ 后，右端要求上格等于 $q$，所以直接令

$$f(j+1,c)=H(d,c).$$

下一段的总和必须重新取 $\sum_c f(j+1,c)$，不能沿用尚未施加右端限制的 $S(d)$。实现中最后一步只需要计算 $H(d,c)$，不必再计算随后会丢弃的 $R(d,c),C(d,c),S(d)$。

例如 $m=5$，相邻两列上格分别固定为 $1,2$。第一列有 $f(1)=0$，其余四项为 $1$，故 $s=4$。目标截面初始为零，$R(0,2)=0$。新下格取 $1$ 时有 $4-0-0=4$ 种；取 $3,4,5$ 时各有 $4-0-1=3$ 种；取 $2$ 非法，合计 $13$ 种。

初始化、收尾与适用范围

本子任务第一列已经有预置上格 $p$，所以 $f(1,c)=[c\ne p]$。最后一列也是关键列，最终答案为 $\sum_{c=1}^{m}f(k,c)$。$n=1$ 时不发生段间转移，答案为 $m-1$。

代码顺带处理同一结构下首尾为空的情形。固定一个合法端点列，向外延长一列空白总有 $D$ 种方法，所以初值一般写为

$$f(1,c)=[c\ne p]D^{\ell_1-1},$$

最终答案乘 $D^{n-\ell_k}$。若没有任何预置士兵，答案为 $m(m-1)D^{n-1}$。预处理 $D$ 的幂即可。这没有解除“第二行没有预置士兵”的前提，不能用于一般的上下两行混合预置。

完整转移枚举了所有合法的相邻列，行列和方程是对该转移的精确求和，截面方程也未舍弃会进入目标状态的前驱；在右端保留截面恰好施加了该列的预置条件。因此逐段递推与原来的完整状态 DP 等价。

复杂度

时间复杂度为 $O(nm)$。各段距离之和不超过 $n-1$，每步扫描 $m$ 个兵种，每个关键列重新初始化统计量也只需 $O(m)$；幂表另需 $O(n)$。

空间复杂度为 $O(n+m)$。若保留所有处理位置的 $R,C,H$，最坏需要约 $3nm$ 个整数，在 $n=m=10^4$ 时约为 $1.2$ GB，超过 $512$ MB，因此只保存旧、新两层。所有新层值都从旧层计算，整层完成后交换；关键列上的 $f(j,c)$ 正是筛选后的截面，不另存重复的历史表。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

int norm(i64 x) {
  return (x % mod + mod) % mod;
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i]) pos.push_back(i);
  }
  int ways = norm(1LL * m * m - 3LL * m + 3);
  vector<int> pw(n + 1, 1);
  for (int i = 1; i <= n; i++) pw[i] = 1LL * pw[i - 1] * ways % mod;
  if (pos.empty()) {
    cout << 1LL * m * (m - 1) % mod * pw[n - 1] % mod << '\n';
    return;
  }
  int last = pos[0], p = a[last];
  vector<int> dp(m + 1, pw[last]), ndp(m + 1);
  vector<int> row(m + 1), col(m + 1);
  vector<int> next_row(m + 1), next_col(m + 1);
  dp[0] = dp[p] = 0;
  for (int j = 1; j < (int)pos.size(); j++) {
    int r = pos[j], q = a[r];
    int sum = accumulate(dp.begin(), dp.end(), 0LL) % mod;
    fill(row.begin(), row.end(), 0);
    row[p] = sum;
    col = dp;
    if (p != q) fill(dp.begin(), dp.end(), 0);
    for (int i = last + 1; i <= r; i++) {
      i64 base = 1LL * sum - row[q];
      for (int x = 1; x <= m; x++) {
        ndp[x] = x == q ? 0 : norm(base - col[x] + dp[x]);
      }
      if (i < r) {
        for (int x = 1; x <= m; x++) {
          next_row[x] = norm(1LL * (m - 2) * (sum - row[x]) + col[x]);
          next_col[x] = norm(1LL * (m - 2) * (sum - col[x]) + row[x]);
        }
        row.swap(next_row);
        col.swap(next_col);
        sum = 1LL * sum * ways % mod;
      }
      dp.swap(ndp);
    }
    last = r;
    p = q;
  }
  int ans = accumulate(dp.begin(), dp.end(), 0LL) % mod;
  cout << 1LL * ans * pw[n - 1 - last] % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

用行列和优化列状态转移（通过子任务 1–2，共 20 分）

列状态与不合法前驱

设 $F(i,x,y)$ 为前 $i$ 列已填好，第 $i$ 列上下兵种分别为 $x,y$ 的方案数。$x,y$ 均在 $1\ldots m$ 中；两者相同，或与该列预置不符时，状态恒为零。第一列每个合法状态为 $1$。

对于合法的新列 $(x,y)$，上一列 $(u,v)$ 只需满足 $u\ne x,v\ne y$，因此完整递推为

$$F(i,x,y)=\sum_{\substack{1\le u,v\le m\\u\ne x,\ v\ne y}}F(i-1,u,v).$$

当 $n,m\le500$ 时，状态数量仍可接受，但不能对每个状态重新扫描旧状态。

用容斥同时排除两条水平边冲突

对上一层预先求出

$$S(i-1)=\sum_{u=1}^{m}\sum_{v=1}^{m}F(i-1,u,v),\quad R(i-1,x)=\sum_{v=1}^{m}F(i-1,x,v),\quad C(i-1,y)=\sum_{u=1}^{m}F(i-1,u,y).$$

从所有旧方案中，扣掉旧上格为 $x$ 的方案、旧下格为 $y$ 的方案。旧列恰为 $(x,y)$ 的方案被扣了两次，需要加回一次：

$$F(i,x,y)=S(i-1)-R(i-1,x)-C(i-1,y)+F(i-1,x,y)\pmod P.$$

例如新列为 $(2,4)$，两类冲突分别是旧列形如 $(2,v)$ 和 $(u,4)$，交集恰为 $(2,4)$。这里加回旧状态不是允许冲突，而是把被扣两次的交集恢复到“恰好扣一次”。

每次先从完整旧层统计总和、行和、列和，再枚举合法的新状态，按该式赋值；不符合新列预置的状态保持零。所有等式都在模 $P=10^9+9$ 下计算，减法要归一化。

最后输出

$$\sum_{x=1}^{m}\sum_{y=1}^{m}F(n,x,y)\pmod P.$$

状态保留全部可能的最后一列，递推恰好检查所有新出现的边；归纳可知它计算了所有合法方案，包括答案为零的情况。

时间复杂度为 $O(nm^2)$。每层两次扫描兵种对，分别统计旧层和填写新层。空间复杂度为 $O(nm^2)$，保留完整按列状态；在 $n,m\le500$ 的保证范围内，状态与容器合计仍在题目 512 MB 限制内。该方法覆盖子任务 1、2。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1)));
  for (int x = 1; x <= m; x++) {
    for (int y = 1; y <= m; y++) {
      if (x != y && (!a[0] || a[0] == x) && (!b[0] || b[0] == y)) dp[0][x][y] = 1;
    }
  }
  for (int i = 1; i < n; i++) {
    vector<int> row(m + 1), col(m + 1);
    i64 sum = 0;
    for (int x = 1; x <= m; x++) {
      for (int y = 1; y <= m; y++) {
        int value = dp[i - 1][x][y];
        row[x] = (row[x] + value) % mod;
        col[y] = (col[y] + value) % mod;
        sum += value;
      }
    }
    sum %= mod;
    for (int x = 1; x <= m; x++) {
      for (int y = 1; y <= m; y++) {
        if (x == y || (a[i] && a[i] != x) || (b[i] && b[i] != y)) continue;
        i64 value = sum - row[x] - col[y] + dp[i - 1][x][y];
        dp[i][x][y] = (value % mod + mod) % mod;
      }
    }
  }
  i64 ans = 0;
  for (int x = 1; x <= m; x++) {
    for (int y = 1; y <= m; y++) ans += dp[n - 1][x][y];
  }
  cout << ans % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

按列枚举并合并一维前驱（通过子任务 1，共 10 分）

固定一列的两个兵种

当 $n,m\le50$ 时，可以直接记录最后一列上下格子的兵种。设 $F(i,x,y)$ 为已经填好前 $i$ 列，且第 $i$ 列上下兵种分别为 $x,y$ 的方案数，$1\le x,y\le m$。

若 $x=y$，或者 $x,y$ 不符合该列已驻扎士兵的兵种，状态为零。第一列每个合法状态的值为 $1$。

往右增加一列，只多出上下两条水平边和新列的一条竖边。竖边已由新状态 $x\ne y$ 保证。旧列上下为 $u,v$ 时，剩余条件恰好是 $u\ne x,v\ne y$，故

$$F(i,x,y)=\sum_{\substack{1\le u,v\le m\\u\ne x,\ v\ne y}}F(i-1,u,v)$$

对所有合法新状态成立。每个完整方案都有唯一的上一列状态，因此上述求和没有遗漏或重复。

先合并一个枚举维度

直接枚举 $(x,y,u,v)$ 太慢。先求旧层按上格兵种分类的总数

$$R(i-1,u)=\sum_{v=1}^{m}F(i-1,u,v).$$

固定旧上格为 $u$ 后，只须从该行总和扣掉旧下格恰为 $y$ 的状态，因此

$$F(i,x,y)=\sum_{\substack{1\le u\le m\\u\ne x}} \bigl(R(i-1,u)-F(i-1,u,y)\bigr)\pmod P.$$

例如新列为 $(2,4)$，旧上格不能为 $2$；对其他每个旧上格，从整行中去掉旧下格为 $4$ 的方案即可。即使原始预置已经冲突，也只会导致相应状态为零，无需更改题意或单独假设存在合法方案。

按 $i=2,\ldots,n$ 推进，每层先完整计算旧层行和，再填新层。最终答案为

$$\sum_{x=1}^{m}\sum_{y=1}^{m}F(n,x,y)\pmod P,\qquad P=10^9+9.$$

时间复杂度为 $O(nm^3)$：每层求行和用 $O(m^2)$，每个新状态再枚举 $m$ 个旧上格。空间复杂度为 $O(nm^2)$，保存完整的按列状态。该方法适用于子任务 1；扩大 $m$ 后三重循环迅速成为瓶颈。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 1000000009;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int& x : a) cin >> x;
  for (int& x : b) cin >> x;
  vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1)));
  for (int x = 1; x <= m; x++) {
    for (int y = 1; y <= m; y++) {
      if (x != y && (!a[0] || a[0] == x) && (!b[0] || b[0] == y)) dp[0][x][y] = 1;
    }
  }
  for (int i = 1; i < n; i++) {
    vector<int> row(m + 1);
    for (int x = 1; x <= m; x++) {
      row[x] = accumulate(dp[i - 1][x].begin(), dp[i - 1][x].end(), 0LL) % mod;
    }
    for (int x = 1; x <= m; x++) {
      for (int y = 1; y <= m; y++) {
        if (x == y || (a[i] && a[i] != x) || (b[i] && b[i] != y)) continue;
        i64 sum = 0;
        for (int u = 1; u <= m; u++) {
          if (u != x) sum += row[u] - dp[i - 1][u][y];
        }
        dp[i][x][y] = (sum % mod + mod) % mod;
      }
    }
  }
  i64 ans = 0;
  for (int x = 1; x <= m; x++) {
    for (int y = 1; y <= m; y++) ans += dp[n - 1][x][y];
  }
  cout << ans % mod << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}