考虑怎么求单独一块区域的贡献。显然不上升和不下降贡献相等。如果一块区域有 a 栋高楼,b 个高度可以选,则相当于 a 个相同的球放入 b 个不同的盒子 的方案数。根据小学二年级(?的数学知识,可以将其看做 a+b 个相同的球放到 b 个不同的盒子中,每个盒子至少放一个球,插板法即可得 \binom{a+b-1}{b-1}。
为什么是 a 个相同的球?因为题目要求高楼高度不上升/不下降,所以方案与是什么高楼无关,只和每个高楼的高度有关。
根据乘法原理,将上述四块区域的贡献相乘即为 x,y=i 时的方案数。
Case 2:x,y\leq n 或 x,y>n。
将 [x,y] 中间的高楼看成一个高楼,则根据 Case 1 的 trick,答案为 \binom{n+m-1}{m-1}\times\binom{n+x-y+m-1}{m-1}。
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
const int p=998244353;
ll ksm(ll a,ll b){ll s=1,m=a; while(b){if(b&1)s=s*m%p; m=m*m%p,b>>=1;} return s;}
ll m,n,x,y,ans,fc[N],ifc[N];
ll C(ll m,ll n){return fc[n+m-1]*ifc[n]%p*ifc[m-1]%p;}
int main(){
cin>>m>>n>>x>>y;
fc[0]=1; for(int i=1;i<=m+n;i++)fc[i]=fc[i-1]*i%p;
ifc[m+n]=ksm(fc[m+n],p-2); for(int i=m+n-1;~i;i--)ifc[i]=ifc[i+1]*(i+1)%p;
if(x<=n&&y>n)for(int i=1;i<=m;i++)ans=(ans+C(i,x-1)*C(m-i+1,n-x)%p*C(m-i+1,y-n-1)%p*C(i,2*n-y))%p;
else ans=C(m,n)*C(m,n+x-y)%p;
cout<<ans<<endl;
return 0;
}
```
写的比较匆忙,如有笔误还请尽快指出,感激不尽!
Upd on 2020.5.3:修改部分文字和代码。