题解 P6475 【[NOI Online #2 入门组] 建设城市】
P6475 [NOI Online #2 入门组] 建设城市
题目大意：
共有 \(2n\) 个位置，现在要给每个位置填上一些数，使得 \(x,y\) 位置上的数相等， \([1,n]\) 单调不减， \((n,2n]\) 单调不增，最大数不超过 \(m\) 。
sulotion：
可知 \(n\) 处的数字是 \(m\) 。
组合数学，分情况讨论：
- \(x,y\) 分居 \(n\) 两侧：
我们不妨设 \(x,y\) 的数是 \(i\) 。分四段考虑：
- \([1,x)\) 相当于有 \(i\) 个抽屉， \(x\) 个小球，有几种放法，根据插板发，现在每个抽屉里放个小球，现在有 \(i+x-1\) 个球 \(i+x-2\) 个空，要插 \(i-1\) 个板，可得方案数 \(C_{i+x-2,i-1}\) 。为了方便现在设 \(F_{a,b}=C_{a+b-1,b-1}\) 。
- \([x,n]\) 同理，\(F_{n-x,m-i+1}\)。
- \((n,y)\) \(F_{i-n-1,m-i+1}\)。
- \([y,2n]\) \(F_{2n-y,i}\)。
根据乘法原理，把上述柿子乘起来即是答案。
- \(x,y\) 位于同侧：
由于需要递增/递减，所以\([x,y]\) 中的高度需要相等，看成一个即可。
\(ans=F_{n,m}\times F_{n+x-y,m}\)。
细节处理：
- \(\text{longlong}\)
- 插板法中 \(n+m-1\) 相应的要开大数组
代码
#include
using namespace std;
typedef long long LL;
const int N=1e5+5,p=998244353;
int fat[N*2],inv[N*2];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=(LL)res*a%p;
a=(LL)a*a%p;
b>>=1;
}
return res;
}
void init(){
fat[0]=1;
for(int i=1;i<=200000;i++)
fat[i]=(LL)fat[i-1]*i%p;
inv[200000]=qpow(fat[200000],p-2);
for(int i=199999;i>=0;i--)
inv[i]=(LL)inv[i+1]*(i+1)%p;
}
int C(int n,int m){
return (LL)fat[n]*inv[m]%p*inv[n-m]%p;
}
int F(int a,int b){
return C(a+b-1,b-1);
}
int ans;
void cal1(int m,int n,int x,int y){
for(int i=1;i<=m;i++)
ans=((LL)ans+(LL)F(x-1,i)*F(n-x,m-i+1)%p*F(y-n-1,m-i+1)%p*F(2*n-y,i)%p)%p;
}
void cal2(int m,int n,int x,int y){
ans=(LL)F(n,m)*F(n+x-y,m)%p;
}
int main(){
init();
int m,n,x,y;
scanf("%d%d%d%d",&m,&n,&x,&y);
if(x<=n&&y>n) cal1(m,n,x,y);
else cal2(m,n,x,y);
printf("%d",ans);
return 0;
}