L

题意：
给出一个 有 n 行的矩阵
每行有 n - i + 1 列
每行的最后一个格子都是美梦格子
询问：从 1 开始能走到任何一个美梦格子且不经过噩梦格子的方案数
关于组合数的推导过程可以去看牛子营的L讲解
这里仅给出一个新的思路
思路：
定义 f[i] 从 1 到 第 i 个 障碍 且途中 不经过其他障碍方案数
利用容斥,我们枚举能经过的障碍 j
那么转移方程如下:
f[i] = C(xi - 1, xi + yi - 2) - 
       f[j] * ∑(1, i) C(xi - xj, xi + yi - xj - yj);
如此,我们有 n 个不同的答案格子
所以我们枚举有哪些答案格子能被当成终点转移过来即可
因为终点可以定义为 第 m + 1 个障碍
那么我们的答案不正是 f[m + 1] 么，如此累加即可


#include<bits/stdc++.h>
#define ll long long
#define int long long
#define x first
#define y second
using namespace std;
const int maxN = 5e5 + 10;
const int maxM = 2e5 + 10;
const int INF = 1e18;
const int mod = 1e9 + 7;
inline int read()
{
    int ans=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return f?-ans:ans;
}
int n, m, k;
int fact[maxN], infact[maxN];
int qmi(int a,int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = a * res % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}
int C(int a,int b)
{
    if(a > b)return 0;
    else
        return fact[b] * infact[b - a] % mod * infact[a] % mod;   //C(n,m) = m! / (m - n)! * n! 
}
void init()
{
    fact[0] = infact[0] = 1;
    for(int i = 1 ; i < maxN ; i++)
    {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i,mod - 2) % mod;
    }
}
int f[3010];

pair<int,int> a[3010];
signed main()
{
    
    init();
    n = read(), m = read();
    for(int i = 1 ; i <= m ; i++)
    {
        int x = read(), y = read();
        a[i] = {x,y};
    }
    sort(a + 1, a + 1 + m);
    for(int i = 1 ; i <= m ; i++)
    {
        int sum1 = a[i].x + a[i].y;
        f[i] = C(a[i].x - 1, a[i].x + a[i].y - 2);
        for(int j = 1 ; j <= i - 1 ; j++)
        {
            if(a[j].y <= a[i].y)
            {
                int sum2 = a[j].y + a[j].x;
                f[i] = (f[i] - (f[j] * 
                        C(a[i].x - a[j].x, sum1 - sum2)) % mod + mod) % mod;
            }
        }
    }
  //上述是对非终点障碍的预处理;
    int ans = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int t = C(i - 1, n + 1 - 2); //枚举终点格子
        int x = n - i + 1, y = i;
        int sum1 = x + y;
        for(int j = 1 ; j <= m ; j++) //枚举障碍格子
        {
            if(x >= a[j].x && y >= a[j].y) 
            //保证终点格子一定是在这些障碍格子的下方
            {
                int sum2 = a[j].x + a[j].y;
                t = (t - (f[j] * 
                     C(y - a[j].y, sum1 - sum2)) % mod + mod) % mod;
            }
        }
        ans += t;
        ans %= mod;
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}