AT_abc037_d 题解

Lele_Programmer · 2024-08-30 22:19:29 · 题解

AT_abc037_d 题解

思路

拓扑排序。

对于一个点，如果上下左右四个方向的某个点比它大，则连一条边。因为连边可以表示一种递增关系，所以可以证明不存在环，因此最后将会构建出一张 DAG（有向无环图）。

设 f_u 为以点 u 为结束点的路径数量，设 v 这个点可以从 u 走一步走到，则 f_v = \sum f_u。

做一遍拓扑排序即可。

代码

代码中将二维数组转换成图中的点的时候，从左往右从上到下依次编号。

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

#define endl '\n'
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define _rep(i,a,b) for (int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for (int i=(a);i<=(b);c)
#define _rrep(i,a,b) for (int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for (int i=(a);i>=(b);c)
#define _iter(i,a) for (auto i=a.begin();i!=a.end();++i)
#define _graph(i,u) for (int i=h[u];~i;i=ne[i])

const int N=1000005;
const int M=4000005;
const int K=1005;
const int mod=1e9+7;

int n,m;
int arr[K][K];
int e[M],ne[M],h[N],tot;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int in[N],f[N];
queue<int> q;

void add(int a,int b) {
    e[tot]=b,ne[tot]=h[a],h[a]=tot++;
}

int get(int i,int j) {
    return (i-1)*m+j;
}

bool check(int i,int j) {
    return i>=1 && i<=n && j>=1 && j<=m;
}

void topu() {
    _rep(i,1,n) _rep(j,1,m) f[get(i,j)]=1;
    _rep(i,1,n) _rep(j,1,m) if (!in[get(i,j)]) q.push(get(i,j));
    while (!q.empty()) {
        int u=q.front(); q.pop();
        _graph(i,u) {
            f[e[i]]=(f[e[i]]+f[u])%mod;
            if (!--in[e[i]]) q.push(e[i]);
        }
    }
}

int main() {
    memset(h,-1,sizeof(h));
    scanf("%d %d",&n,&m);
    _rep(i,1,n) _rep(j,1,m) scanf("%d",&arr[i][j]);
    _rep(i,1,n) _rep(j,1,m) _rep(k,0,3) if (check(i+dx[k],j+dy[k]) && arr[i+dx[k]][j+dy[k]]>arr[i][j]) add(get(i,j),get(i+dx[k],j+dy[k])),in[get(i+dx[k],j+dy[k])]++;
    topu();
    int ans=0;
    _rep(i,1,n) _rep(j,1,m) ans=(ans+f[get(i,j)])%mod;
    printf("%d",ans);
    return 0;
}