魔改森林

题意：
有一个n行m列的网格图，起点在格点(n+1，1), 终点在(1,m+1),有k个格点是不能走的障碍点。求从起点到终点的路线有多少种？（只能向上或向右）

思路：
从数据范围看当n,m<=1000时我们可以用动态规划解决：
dp[n+1][1]=1;
dp[i][j]=dp[i+1][j]+dp[i][j-1]
当n,m超过1000时，我们发现k很小，所以可以用组合数和容斥解决：
从（x,y）到（x2,y2)的路线方式数目为C(x-x2,x-x2+y2-y)（既有（x-x2+y2-y）步，其中选择了（x-x2）步向上走）;

代码：

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=998244353;

ll d[1005][1005], dp[1005][1005];

ll qpow(ll n,ll m)
{
    ll z=1;
    while(m)
    {
        if(m&1)
        {
            z=z*n%inf;
        }
        n=n*n%inf;
        m>>=1;
    }
    return z;
}

ll C(ll n,ll m)
{
   if(m-n<n)
   {
       n=m-n;
   }
   ll x=1, y=1;
   for(ll i=1, j=m;i<=n;i++,j--)
   {
       x=x*j%inf;
       y=y*i%inf;
   }
   x=x*qpow(y,inf-2)%inf;
   return x;
}

struct w
{
    ll x, y;
}w[5];

ll ans=0;

ll n, m, k;

void rongchi(int i,int flag,ll x,ll y, ll v,int o)
{
    if(i==k)
    {
        v=v*C(x-1,x-1+m+1-y)%inf;
        //printf("v=%lld %d %lld\n",v,flag,o);
        ans=(ans+v*flag+inf)%inf;
    }
    else
    {
        if(w[i].x<=x&&w[i].y>=y)
        {
            ll vi=v*C(x-w[i].x,x-w[i].x+w[i].y-y)%inf;
            rongchi(i+1,-flag,w[i].x,w[i].y,vi,o+1);
        }
        rongchi(i+1,flag,x,y,v,o);
    }
}

bool cmp(struct w a,struct w b)
{
    if(a.x!=b.x)
    {
        return a.x>b.x;
    }
    return a.y<b.y;
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    if(n<=1000&&m<=1000)
    {
        for(int i=0;i<k;i++)
        {
            int x, y;
            scanf("%d%d",&x,&y);
            d[x][y]=1;
        }
        dp[n+1][1]=1;
        for(int i=n+1;i>=1;i--)
        {
            for(int j=1;j<=m+1;j++)
            {
                if(d[i][j]==1)
                {
                    continue;
                }
                dp[i][j]=(dp[i][j]+dp[i+1][j]+dp[i][j-1])%inf;
            }
        }
        cout << dp[1][m+1] << endl;
    }
    else
    {
        for(int i=0;i<k;i++)
        {
            scanf("%lld%lld",&w[i].x,&w[i].y);
        }
        sort(w,w+k,cmp);
        rongchi(0,1,n+1,1,1,0);
        cout << ans << endl;
    }
    return 0;
}