题意
题目链接
sol
(f[i][j])表示前(i)行(j)列的贡献,转移的时候枚举从哪里转移而来,复杂度(o(n^4))
然后考虑每一行的贡献,动态开节点线段树维护一下每种颜色的答案
转移的时候用总的方案减去相同颜色的方案
复杂度(o(n^2 log^2 n))
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1001, inf = 1e9 + 10, mod = 1000000007, ss = maxn * maxn * 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int add(int x, int y) { if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y; } int n, m, k, c[maxn][maxn], f[maxn][maxn], tot; int root[ss], ls[ss], rs[ss], sum[ss]; void intadd(int &k, int l, int r, int pos, int val) { if(!k) k = ++tot; sum[k] = add(sum[k], val); if(l == r) return ; int mid = l + r >> 1; if(pos <= mid) intadd(ls[k], l, mid, pos, val); else intadd(rs[k], mid + 1, r, pos, val); } int query(int k, int l, int r, int ll, int rr) { if(!k) return 0; if(ll <= l && r <= rr) return sum[k]; int mid = l + r >> 1; if(ll > mid) return query(rs[k], mid + 1, r, ll, rr); else if(rr <= mid) return query(ls[k], l, mid, ll, rr); else return add(query(ls[k], l, mid, ll, rr), query(rs[k], mid + 1, r, ll, rr)); } signed main() { n = read(); m = read(); k = read(); f[1][1] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { int k = read(); c[i][j] = k; if(!f[i][j]) f[i][j] = add(query(root[0], 1, m, 1, j - 1), -query(root[k], 1, m, 1, j - 1)); } for(int j = 1; j <= m; j++) intadd(root[0], 1, m, j, f[i][j]), intadd(root[c[i][j]], 1, m, j, f[i][j]); } cout << f[n][m]; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605682.html