T1

分析

对于 n,m<=1000 的点直接使用DP即可可得20分
对于 n,m<=100000 的点我们可以发现k很小
考虑使用容斥原理
我们定义一个work函数
work是指右移a次上移b次有多少种移法

work解决方法：

1.考虑把b次上移插入a次右移动的空中 a有a+1个空所以a++
2.问题转变为类似放苹果的问题即：有b个苹果，放入a个不同的盘子有多少种放法（盘子可以为空）
3.既然盘子可以为空，但是考虑插空做法盘子不能为空苹果数+=盘子数即 b+=a
4.考虑插空，有a个盘子，所以有a+1个插板，但是最两边的空一定有插板， a++，a-=2；即a--
5.b个苹果有b+1个空，但是最两边的空一定有插板， b++，b-=2；即b--
6.调用组合数得出答案

work代码如下

LL work(LL a,LL b) {
    a++;
    b+=a;
    b--;
    a--;
    return C(a,b);
}

updata 2021.2.3

work函数最开始想复杂了
其实就是在(a+b)的序列内,选a次作为右移即可
即C(a,a+b)

如果求逆元用线性求逆元会更快一些

关于容斥

1.ans+没有障碍的情况
2.如果有障碍，枚举每个障碍求出经过这个障碍的路径有多少条，减去（如何求见代码，思维难度不大）
3.如果k>=2 , 枚举每2个障碍求出经过这2个障碍的路径有多少条，加（如何求见代码，思维难度不大）
3.如果k==2 , 求出经过这3个障碍的路路径有多少条，减去（如何求见代码，思维难度不大）

#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);
}
LL C(LL a,LL b) {
    LL a1=1;
    for(LL i=b; i>=b-a+1; i--)
        a1=a1*i%mod;
    for(LL i=1; i<=a; i++)
        a1=(a1*ni[i])%mod;
    return a1;
}
LL work(LL a,LL b) {
    a++;
    b+=a;
    b--;
    a--;
    return C(a,b);
}
int main() {
    cin>>n>>m>>k;
    m++;n++;
    if(n<=1000&&m<=1000) {
        for(LL i=1; i<=k; i++) {
            cin>>s>>t;
            f[s][t]=1;
        }
        dp[n][1]=1;
        for(LL i=n; i>0; i--)
            for(LL j=1; j<=m; j++)
                if((i!=n||j!=1)&&f[i][j]!=1)
                    dp[i][j]=(dp[i+1][j]+dp[i][j-1])%mod;
        cout<<dp[1][m]<<"\n";
    }
    else {
        csh();
        LL ans=work(n-1,m-1);
        for(LL i=1; i<=k; i++) {
            cin>>x[i]>>y[i];
            x[i]=n-x[i];
            y[i]--;
            ans=(ans-work(x[i],y[i])*work(n-x[i]-1,m-y[i]-1))%mod;
        }
        for(LL i=1; i<=k; i++)
            for(LL j=i+1; j<=k; j++)
                if(x[i]+y[i]>x[j]+y[j]) {
                    swap(x[i],x[j]);
                    swap(y[i],y[j]);
                }
        if(k>=2)
            for(LL i=1; i<=k; i++)
                for(LL j=i+1; j<=k; j++)
                    if(x[j]>=x[i]&&y[j]>=y[i])
                        ans=(ans+work(x[i],y[i])*work(x[j]-x[i],y[j]-y[i])%mod*work(n-x[j]-1,m-y[j]-1))%mod;
        if(k==3)
            if(x[3]>x[2]&&x[2]>x[1])
                if(y[3]>y[2]&&y[2]>y[1])
                    ans-=work(x[1],y[1])*work(x[2]-x[1],y[2]-y[1])%mod*work(x[3]-x[2],y[3]-y[2])%mod*work(n-x[3]-1,m-y[3]-1)%mod;
        cout<<(ans+mod)%mod<<endl;
    }
    return 0;
}

魔改森林

T1

分析

work解决方法：

work代码如下

updata 2021.2.3

关于容斥