魔改森林

题意：

曾经有一道叫做迷雾森林的题目，然而牛牛认为地图中的障碍太多，实在是太难了，所以删去了很多点，出了这道题。

牛牛给出了一个n行m列的网格图
初始牛牛处在最左下角的格点上(n+1,1)，终点在右上角的格点(1,m+1)
现在它想知道，从起点走到终点，只能向上或向右走，一共有多少种走法呢？

需要注意的是，除了起点和终点外，其它的每个格点都有可能有障碍，无法通过。

请注意格子与格点的区别

题解：

参考博客
对于 n,m<=1000 的点：DP
对于 n,m<=100000 的点，因为k很小，考虑使用容斥原理，我们定义一个work函数，work是指右移a次上移b次有多少种移法

假设只有一个点(x,y)不能走，总方案是C(m+n,n),减去经过这个点方案C(x+y,x) * C(n-x+n-y,n-x)
即 C(m+n,n)- C(x+y,x) * C(n-x+n-y,n-x)
如果有多个障碍点的话，我们考虑什么样的点彼此会共同影响，
图中绿色为障碍点，蓝色为路线，我们不难发现当点与点之间存在偏序关系的时候，就会彼此共同影响，如何找偏序关系，当
(x[j]>=x[i]&&y[j]>=y[i])（i是左下方的点，j是右上方的点）时说明满足条件

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,k,s,t;
bool f[1005][1005];
LL dp[1005][1005];
LL x[10],y[10];
LL mod=998244353;
LL ksm(LL a) {
    LL b=mod-2;
    LL ans=1;
    while(b) {
        if(b&1)
            ans=(a*ans)%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
LL ni[100005];
void csh() {
    for(LL i=1; i<=100000; i++)
        ni[i]=ksm(i);