题解：[ARC074E] RGB Sequence
喵仔牛奶
·
·
题解
tag：DP 优化
Solution
设 $f_{i,j,k}$ 表示从 $a_i$ 往前，第一个与 $a_i$ 颜色不同的是 $a_j$，第一个颜色与 $a_i,a_j$ 都不相同的是 $a_k$ 的方案数。
每次需要做的是将不合法状态置零，转移到 $i+1$。
将 $j,k$ 看着横纵两维，观察每次的操作：
- 将不合法状态置零相当于之保留一个矩阵，将这个矩阵之外的状态置为 $0$。
- 转移到 $i+1$ 时有三种 $(j,k),(i,k),(i,j)$。第一种滚动数组时自动继承，什么也不干；后面两种第一维都是 $i$，相当于加入一行。
我们维护 $s_i=\sum_{j=1}^{n}f_{now,i,j}+f_{now,j,i}$，这样可以 $\mathcal{O}(n)$ 加入一行。因为每次加入一行，所以非 $0$ 的状态总共只有 $\mathcal{O}(n^2)$ 个，如果可以 $\mathcal{O}(1)$ 找到一个要置零的数，就可以 $\mathcal{O}(n^2)$ 完成置零。
维护 $A_i,B_i$ 表示第 $i$ 行 / 第 $i$ 列当前的非零状态的集合。每次删除时枚举不合法的行列，枚举行列中的数删除并打上删除标记，并清空对应的集合。一个数可能在行集合被删除后在列集合中仍然存在，但我们打上了删除标记，遇到不要管就行了。
总复杂度 $\mathcal{O}(n^2+m)$。
# Code
```cpp
namespace Milkcat {
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e6 + 5, mod = 1e9 + 7;
typedef Math::Mint<mod> MI;
int n, m, x, y, z; MI s[N], t[N];
vector<pii> g[N]; vector<MI> f; vector<int> p, q, A[N], B[N];
void ins(int x, int y, MI v) {
if (v == 0) return;
int b = SZ(f); f.pb(v), p.pb(x), q.pb(y);
A[x].pb(b), B[y].pb(b), s[x] += v, s[y] += v;
} // 加入状态 f[x][y]=v
int main() {
cin >> n >> m;
REP(i, 1, m)
cin >> x >> y >> z, g[y].pb(x, z);
ins(0, 0, 1);
REP(i, 0, n) {
int pl = 0, pr = 1e9, ql = 0, qr = 1e9;
for (auto [j, x] : g[i]) {
if (x == 1) pr = min(pr, j - 1);
if (x == 2) pl = max(pl, j), qr = min(qr, j - 1);
if (x == 3) ql = max(ql, j);
} // 求出 j,k 的取值范围
REP(j, 0, i) {
if (j >= pl && j <= pr) continue;
for (int x : A[j])
s[p[x]] -= f[x], s[q[x]] -= f[x], f[x] = 0;
A[j].clear();
}
REP(j, 0, i) {
if (j >= ql && j <= qr) continue;
for (int x : B[j])
s[p[x]] -= f[x], s[q[x]] -= f[x], f[x] = 0;
B[j].clear();
} // 置零
if (i < n) {
REP(j, 0, i) t[j] = s[j];
REP(j, 0, i) ins(i, j, t[j]);
} // 转移到 i+1
}
MI rs = 0;
REP(i, 0, n) {
rs += s[i], s[i] = 0;
A[i].clear(), B[i].clear(), g[i].clear();
}
f.clear(), p.clear(), q.clear();
cout << rs / 2 << '\n'; // f[i][j] 被计算了两次！
return 0;
}
}
```