自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:21:08，当前版本为作者最后更新于2020-04-25 19:38:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门。

前置知识：组合数学（P3811 【模板】乘法逆元，利用乘法逆元求组合数）。

题目没有告诉我们 $x,y$ 是否是在 $n$ 的两侧，所以要分情况讨论。

• Case $1$：$x\leq n<y$。

  枚举 $x,y$ 的高度。假设当前 $x,y$ 的高度为 $i$，则：

  • $x$ 左边的 $x-1$ 个高楼高度范围为 $[1,i]$。
  • $x$ 右边 $n$ 左边（包含 $n$）的 $n-x$ 个高楼高度范围为 $[i,m]$。
  • $n$ 右边（不包含 $n$）$y$ 左边的 $y-n-1$ 个高楼高度范围为 $[i,m]$。
  • $y$ 右边的 $2n-y$ 个高楼高度范围为 $[1,i]$。

  考虑怎么求单独一块区域的贡献。显然不上升和不下降贡献相等。如果一块区域有 $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}$。

$O(n)$ 预处理阶乘及其逆元即可做到 $O(n)$ 求答案。

#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：修改部分文字和代码。