T1

Solution

的部分可以用 的 解决。

到一个点 的所有方案数等于 。

先将障碍点按坐标排序，记 为到第 个点的合法方案数，则

当且仅当

由 的定义可知不会重复排除非法情况。所以可以线性求逆元，再进行 的 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
struct node{
    ll x;
    ll y;
}a[maxn];
ll n,m,k,inv[maxn],f[maxn],ans[maxn];
ll vis[1010][1010],dp[1010][1010];
bool cmp(node u,node v){
    if(u.x!=v.x)
        return u.x>v.x;
    return u.y<v.y;
}
ll C(ll u,ll v){
    return f[u]*inv[v]%mod*inv[u-v]%mod;
}
int main(){
    cin>>n>>m>>k;
    if(n<=1000&&m<=1000){
        n++,m++;
        int u,v;
        for(int i=1;i<=k;i++){
            cin>>u>>v;
            vis[u][v]=1;
        }
        dp[n+1][1]=1;
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
                if(!vis[i][j])
                    dp[i][j]=(dp[i+1][j]+dp[i][j-1])%mod;
        cout<<dp[1][m];
        return 0;
    }
    n++,m++;
    for(int i=1;i<=k;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+k+1,cmp);
    a[k+1].x=1,a[k+1].y=m;
    k++;
    inv[0]=inv[1]=f[1]=1;
    for(int i=2;i<maxn;i++)
        inv[i]=((mod-mod/i)*inv[mod%i])%mod,f[i]=i;
    for(int i=2;i<maxn;i++)
        inv[i]=(inv[i]*inv[i-1])%mod,f[i]=(f[i]*f[i-1])%mod;
    for(int i=1;i<=k;i++){
        ans[i]=C(n-a[i].x+a[i].y-1,a[i].y-1);
        for(int j=1;j<i;j++)
            if(a[j].x>=a[i].x&&a[j].y<=a[i].y)
                ans[i]=(ans[i]+mod-(ans[j]*C(a[j].x+a[i].y-a[i].x-a[j].y,a[j].x-a[i].x)%mod))%mod;
    }
    cout<<ans[k];
    return 0;
}