时间戳

首页 > 技术文章 > Luogu P6475

Luogu P6475

PYD1 2020-08-19 12:48 原文

审题

P6475

略

分析

题目中给了我们如下的条件

  • 楼的编号为\(1-2n\)
  • 高度均为正整数且不超过\(m\)
  • 前n座楼高度不下降，后n座楼高度不上升（即像一座山的形状）
  • \(x,y\)两楼高度相等

我们发现只有最后一个条件比较特殊，所以尝试从最后一个条件入手。

经过简单的思考，不难得到，这道题目有两种情况：\(x,y\)不在同一侧，\(x,y\)在同一侧

1° 当\(x,y\)不在同一侧时，即\(1\le x\le n<y\le2n\)时

我们可以考虑将其分为四段来计算:

\(1 \ -\ x,x+1 \ - \ n,n+1 \ - \ y,y + 1 \ - \ 2n\)

不妨设\(x,y\)的高度都为\(i\)

则我们要计算的就是：

  • \(x-1\)座高楼（\(x\)高度已固定，\(y\)同理）高度不超过\(i\)
  • \(n-x\)座高楼高度在\(i\ - \ m\)范围内（即高度不超过\(m-i+1\)）
  • \(y-n-1\)座高楼高度在\(i\ - \ m\)范围内（即高度不超过\(m-i+1\)）
  • \(2n-y\)座高楼高度不超过\(i\)

的方案数，再由乘法原理相乘即可得到结果

注意到，其中出现了好几次\(a\)座高楼高度不超过\(b\)的表述，考虑将其写成一个函数\(f(a,b)\)来计算值

要解决这个问题，我们可以把它看成是有\(a\)个小球（高楼）放入\(b\)个盒子（高度），求方案总数的问题

我们可以先在每个盒子里都放上一个小球，现在一共有\(a+b\)个小球，\(b\)个盒子，每个盒子里至少有一个小球，考虑使用插板法：将这些小球摆成一排，在球与球之间的空隙中插入\(b-1\)块板子，第1个板子之前的放入第1个盒子，第2个板子至第1个板子之间的放入第2个盒子……以此类推。

这样，方案总数就被我们转移成了\(a+b-1\)个空隙中选取\(b-1\)个空隙插入板子的问题，熟悉组合数学的同学已经知道，这就是\(C_{a+b-1}^{b-1}\)（不了解的同学可以百度组合数）

而由组合数的定义，我们有\(C_{a+b-1}^{b-1}=\dfrac{(a+b-1)!}{(b-1)!((a+b-1)-(b-1))!}=\dfrac{(a+b-1)!}{(b-1)!a!}\)

（感谢@bluebayou的建议，下方写出另一种理解方式，供大家参考：
\(C_{a+b-1}^{b-1}=C_{a+b-1}^{a}=\dfrac{(a+b-1)!}{a!(a+b-1-a)!}=\dfrac{(a+b-1)!}{a!(b-1)!}\)
）

所以\(f(a,b)=\dfrac{(a+b-1)!}{(b-1)!a!}\)

我们能够计算出\(f(a,b)\)后，用一个for循环从1至\(m\)枚举\(k\)，再计算\(f(x-1,k)*f(n-x,m-k+1)*f(y-n-1,m-k+1)*f(2n-y,k)\)求和即可，即求：

\[\sum_{k=1}^mf(x-1,k)*f(n-x,m-k+1)*f(y-n-1,m-k+1)*f(2n-y,k) \]

2°当\(x,y\)在同一侧时，即\(1\le x<y\le n\)或\(n<x<y\le 2n\)时

我们可以将\([x,y]\)（即\(x\)至\(y\)包括\(x,y\)）这一段高楼合并为一座高楼

分为两部分计算：

  • 左边\(n+x-y\)座高楼高度不超过\(m\)
  • 右边\(n\)座高楼高度不超过\(m\)

当\([x,y]\)这“一栋”大楼获得自己的高度时，我们再把它展开，方案总数不变

所以方案总数为：

\[f(n+x-y,m)*f(n,m) \]

预处理

如果每次求\(f(a,b)\)时都套用\(f(a,b)=\dfrac{(a+b-1)!}{(b-1)!a!}\)来计算，那么每次都要计算阶乘，过于耗时。所以我们考虑预处理，使得我们能够\(O(1)\)计算\(f(a,b)\)

首先

显而易见，我们需要预处理阶乘数组\(jc\)，使得\(jc[i]=i!\)。将\(jc[0]\)赋值为1，然后for \(i\) 从1至\(n+m\)（因为最多就能用到\((n+m-1)!\)），\(jc[i]=jc[i-1]*i\)即可。代码比较简单，如下：（不要忘记取余）

jc[0] = 1;
for (register long long i = 1;i <= n + m;i++) jc[i] = (jc[i - 1] * i) % MOD;

其次

注意到我们实际上并不想知道\(f(a,b)\)，而是想知道\(f(a,b)\% \ MOD\)，又注意到\(f(a,b)\)是一个分式，取余时会用到乘法逆元，所以考虑预处理乘法逆元数组\(ny\)，使得\(i! * ny[i]\equiv 1\ (\bmod \ MOD)\)（即\(ny[i]\)为\(i!\)的乘法逆元）

（不会的同学可以看我的乘法逆元）

代码也很简单，如下：（使用的是费马小定理版本）

long long _pow(long long a,long long k){
	long long ans = 1;
	for (;k;k >>= 1,(a *= a) %= MOD){
		if (k & 1) (ans *= a) %= MOD;
	}
	return ans;
}//快速幂

void init(){
	ny[0] = 1;
	for (register long long i = 1;i <= n + m;i++) ny[i] = _pow(jc[i],MOD - 2);
}

将两个合并，就得到了预处理的代码（快速幂省略）：

void init(){
	for (register long long i = 1;i <= n + m;i++) jc[i] = (jc[i - 1] * i) % MOD;
	for (register long long i = 1;i <= n + m;i++) ny[i] = _pow(jc[i],MOD - 2);
}

由\(jc\)数组和\(ny\)数组，

\[f(a,b) = \dfrac{(a+b-1)!}{(b-1)!a!}\equiv \dfrac{jc[a+b-1]}{jc[b-1]*jc[a]}\equiv jc[a+b-1]*ny[b-1]*ny[a] \ (\bmod \ MOD) \]

所以我们可以写出 \(f\)函数：（不要忘了每乘一项就\(\% MOD\)）

long long f(long long a,long long b){
	return jc[a + b - 1] * ny[a] % MOD * ny[b - 1] % MOD;
}

完整代码

码风不好请见谅

#include <bits/stdc++.h>//万能头，不想用的用#include <cstdio>即可 
using namespace std;

const long long MOD = 998244353;
long long m,n,x,y,jc[2000001] = {1},ny[2000001] = {1},ans;//定义jc阶乘数组，ny逆元数组（注意！这里ny[i]为i!的逆元而不是i的逆元） 

long long _pow(long long a,long long k){
	long long ans = 1;
	for (;k;k >>= 1,(a *= a) %= MOD){
		if (k & 1) (ans *= a) %= MOD;
	}
	return ans;
}//快速幂 

void init(){
	for (register long long i = 1;i <= n + m;i++) jc[i] = (jc[i - 1] * i) % MOD;
	for (register long long i = 1;i <= n + m;i++) ny[i] = _pow(jc[i],MOD - 2);
}//初始化（jc[0]和ny[0]在最初已经被赋值为1，此处不用再赋值 

long long f(long long a,long long b){
	return jc[a + b - 1] * ny[a] % MOD * ny[b - 1] % MOD;
}//f函数，具体解释请看上文“初始化”部分 

int main(){
	scanf("%d %d %d %d",&m,&n,&x,&y),init();//读入&初始化 
	if (x <= n && y > n){//如果x,y不在同一侧 
		for (register long long i = 1;i <= m;i++) ans = (ans + f(x - 1,i) * f(n - x,m - i + 1) % MOD * f(y - n - 1,m - i + 1) % MOD * f(n * 2 - y,i) % MOD) % MOD;//计算，求和 
	}else ans = f(n,m) * f(n + x - y,m) % MOD;//否则即为x,y在同一侧，计算 
	printf("%d",ans);//输出答案 
	return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿

推荐阅读