前言:

很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理.

思路:

这题前面1000个数据直接dp即可.
后面1e5,直接组合数预处理+容斥原理即可.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e3+5,P=5;
const int mod=998244353;
typedef long long ll;
ll dp[M][M];
ll f[N],ivf[N];
ll ans[P];
bool mp[M][M];
pair<int,int>a[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }return res;
}

ll C(ll a,ll b)
{
    return f[a]*ivf[b]%mod*ivf[a-b]%mod;
}

void init()
{
    f[0]=1;
    for(int i=1;i<=N-5;i++)    f[i]=f[i-1]*i%mod;
    ivf[N-5]=qp(f[N-5],mod-2);
    for(int i=N-6;i>=0;i--)    ivf[i]=ivf[i+1]*(i+1)%mod;
}

ll cal(ll a,ll b)
{
    return C(a+b,a); 
}

int main()
{
    init();
    int n,m,k,limit=1000;scanf("%d%d%d",&n,&m,&k);n++,m++;
    for(int i=1;i<=k;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        a[i]={n-x+1,y};
    }
    if(n<=limit&&m<=limit)
    {
        for(int i=1;i<=k;i++)    mp[a[i].first][a[i].second]=true;
        dp[0][1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(!mp[i][j]) dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
        printf("%lld\n",dp[n][m]);
    }
    else
    {
        a[++k]={n,m};sort(a+1,a+1+k);
        for(int i=1;i<=k;i++)
        {
            ans[i]=cal(a[i].first-1,a[i].second-1);
            for(int j=1;j<i;j++)
            {
                if(a[j].first<=a[i].first&&a[j].second<=a[i].second)
                {
                    ans[i]-=ans[j]*cal(a[i].first-a[j].first,a[i].second-a[j].second);
                    ans[i]=(ans[i]%mod+mod)%mod;
                }
            }
        }printf("%lld\n",ans[k]);
    }
    return 0;
}