题号 NC200324
名称 魔改森林
来源 牛客OI周赛14-提高组
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：(́安◞౪◟排‵)

分析

对于 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);
}

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

关于容斥

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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目2月3日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴