题解：P3120 [USACO15FEB] Cow Hopscotch G / ARIS0_0 - 13

· · 题解

前言

我怎么在拿线段树爆草 cdq 分治题单。拜谢线段树。

思路

有一个显然的 dp 思路，设 f_{i, j} 表示走到 (i, j) 的方案数。

那么有 f_{i, j} = \sum\limits_{x=1}^{i-1} \sum\limits_{y=1}^{j-1} [ a_{i, j} \neq a_{x, y} ] \cdot f_{x, y}。

其中 [ C ] 的值取决于 C 的真假，如果 C 命题为真，就是 1，否则为 0。

那么考虑前缀和，设 pre_{i, j} = \sum\limits_{x = 1}^{i} \sum\limits_{y = 1}^{i} f_{i, j}。

但是这不够，你需要减掉和自己相同颜色的 f 值，prek_{i, j, k} = \sum\limits_{x = 1}^{i} \sum\limits_{y = 1}^{i} [a_{x, y} = k] f_{i, j}。

那么有 f_{i, j} = pre_{i - 1, j - 1} - prek_{i - 1, j - 1, a_{i, j}}。

但是这玩意还是 O(n^4) 的，和暴力没区别啊。

然后你发现，由于你求值的过程是一行一行来的，所以 pre_{i - 1, j - 1} 可以理解为，当前遍历过的点中 y 小于 j 的所有 f_{x, y} 的和。

这个东西其实不重要，重点是 prek 也可以这么转化。转化万你发现这是一个动态开点线段树可以轻松解决问题。

具体的，根据颜色见线段树，以 y 为修改的位置，f_{i, j} 为修改的值，每次操作就只需要查询，当前这个颜色的线段树中，下标在 1 \sim j - 1 的区间和。

注意一下卡空间即可（其实没有那么卡，只需要注意别开 long long 就能过）。

code

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 755, M = (N - 5) * (N - 5) + 5, mod = 1e9 + 7;

namespace ARIS0_0{
    int n, m, k, a[N][N], f[N][N];

    struct segment{
        int rt[M] = {0}, tr[M * 20] = {0}, ls[M * 20] = {0}, rs[M * 20] = {0}, tot = 0;
        void modify(int &now, int l, int r, int pos, int x){
            if (!now) now = ++ tot;
            tr[now] = (tr[now] + x) % mod;
            if (l == r) return ;
            int mid = (l + r) >> 1;
            if (pos <= mid) modify(ls[now], l, mid, pos, x);
            else modify(rs[now], mid + 1, r, pos, x);
        }
        int query(int now, int l, int r, int lt, int rt){
            if (!now || lt > rt) return 0;
            if (lt <= l && r <= rt) return tr[now];
            int mid = (l + r) >> 1, ans = 0;
            if (lt <= mid) ans = (ans + query(ls[now], l, mid, lt, rt)) % mod;
            if (mid < rt) ans = (ans + query(rs[now], mid + 1, r, lt, rt)) % mod;
            return ans;
        }
    } seg;

    void init(){
    }
    void solve(){
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                cin >> a[i][j];
        f[1][1] = 1, seg.modify(seg.rt[0], 1, n, 1, 1), seg.modify(seg.rt[a[1][1]], 1, n, 1, 1);
        for (int i = 2; i <= n; i ++ ){
            for (int j = 2; j <= m; j ++ )
                f[i][j] = ((seg.query(seg.rt[0], 1, n, 1, j - 1) - seg.query(seg.rt[a[i][j]], 1, n, 1, j - 1)) % mod + mod) % mod;
            for (int j = 1; j <= m; j ++ ) seg.modify(seg.rt[0], 1, n, j, f[i][j]), seg.modify(seg.rt[a[i][j]], 1, n, j, f[i][j]);
        }

        cout << f[n][m] << "\n";
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}
// 你听啊冬至的白雪
// 你听它掩饰着哽咽
// 在没有你的世界
// 再没有你的冬眠
// ARIS0_0 - 13