【每日一题】1月27日题目精讲
题号 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之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
