题目地址：HDUOJ：Problem – 5181

题目描述

Now you have a stack and n numbers 1,2,3,…,n. These n numbers are pushed in the order and popped if the number is at the top of the stack. You can read the sample to get more details.
This question is quite easy. Therefore I must give you some limits.
There are m limits, each is expressed as a pair <A,B> means the number A must be popped before B.
Could you tell me the number of ways that are legal in these limits?
I know the answer may be so large, so you can just tell me the answer mod 1000000007(10^9+7).
一个由1,2,…,n组成的排列，顺次插入栈中，你可以选择在任意时刻弹出栈顶元素，现在有m个要求，要求x必须在y之前出栈，问有多少种合法的出栈顺序。

输入输出格式

输入格式：
The first line contains an integer T(about 5),indicating the number of cases.
Each test case begins with two integers n(1≤n≤300) and m(1≤m≤90000).
Next m lines contains two integers A and B(1≤A≤n,1≤B≤n)
(P.S. there may be the same limits or contradict limits.)

输出格式：
For each case, output an integer means the answer mod 1000000007.

输入输出样例

输入样例#1：

5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1

输出样例#1：

1
42
1
2
0

说明

The only legal pop-sequence of case 3 is 1,2,3.
The legal pop-sequences of case 4 are 2,3,1 and 2,1,3.

题解

我们首先简化问题，不考虑限制，那我们设计状态dp[i][j]表示区间[i, j]内的方案数，枚举区间内最后一个弹出的元素k，那么有下面的方程
dp[i][j] = \sum_{k=i}^j (dp[i][k - 1] * dp[k + 1][j])
有了限制应该怎么办？我们先分析限制对我们转移的影响，假如有限制<A, B>：
如果A<B，包含[A, B]的区间[i, j]，枚举的最后弹出元素为k在(A, B]之间时候显然成立，而如果出现A、B在k的同侧时这个问题会在更小的区间内被解决，不是我们现在考虑的。但是如果k=A时，A就比B晚弹出，这是显然不行的。结论：对于A<B的情况，k≠A。
如果A=B，这种条件并没办法成立，答案直接是0了。
如果A>B，包含[A, B]的区间[i, j]，枚举的最后弹出元素为k不能在(B, A]内。

朴素地思考，我们可以枚举k的时候逐个条件判断一下。但是这样复杂度就成了O(n^3m)，已经无法接受了。
那咋整啊？我们回头来看看一个限制对什么样的区间产生影响。这样的区间[i, j]肯定满足1 \leq i \leq \min(A, B), \max(A, B) \leq j \leq n。我们把区间的两个端点看成二维平面上的一个点，那么这个影响其实是对一个矩形产生的。对于给矩形打标记这种事情，自然可以使用二维差分处理。差分完了以后前缀和求一下，就能查单点了。我们开n个二维平面，枚举k来标记每个k在哪些区间里不能转移即可。这个题巧妙之处就在于把二维差分的思想用进去了。
最后的时间复杂度O(n^3+nm)，空间复杂度O(n^3)。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 305, MO = 1000000007;

int T, n, m, a, b;
LL dp[MAXN][MAXN];
int s[MAXN][MAXN][MAXN];

inline void add(int xa, int ya, int xb, int yb, int dimm) {
    s[xa][ya][dimm]++;
    s[xb + 1][yb + 1][dimm]++;
    s[xb + 1][ya][dimm]--;
    s[xa][yb + 1][dimm]--;
}

int main() {
    T = readint();
    while(T--) {
        memset(dp, 0, sizeof dp);
        memset(s, 0, sizeof s);
        n = readint();
        m = readint();
        bool flag = false;
        for(int i = 1; i <= m; i++) {
            a = readint();
            b = readint();
            if(a == b) flag = true;
            if(a < b) {
                add(1, b, a, n, a);
            } else {
                for(int j = b + 1; j <= a; j++) {
                    add(1, a, b, n, j);
                }
            }
        }
        if(flag) {
            printf("0\n");
            continue;
        }
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    s[i][j][k] += s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k];
                }
            }
        }
        for(int i = 1; i <= n; i++) {
            dp[i][i] = dp[i][i - 1] = 1;
        }
        dp[n + 1][n] = 1;
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for(int k = i; k <= j; k++) {
                    if(!s[i][j][k]) {
                        dp[i][j] = (dp[i][j] + dp[i][k - 1] * dp[k + 1][j] % MO) % MO;
                    }
                }
            }
        }
        printf("%lld\n", dp[1][n]);
    }
    return 0;
}