【解题报告】洛谷P6475 建设城市

题目链接

https://www.luogu.com.cn/problem/P6475

思路

考虑排列组合

  • 如果两个分居左右

我们可以枚举一下两个楼房的高度,假设 x<n<yx<n<y ，那么 xx 左边有 x−1x-1 个楼房，右边有 n−xn-x 个楼房，我们设我们已经枚举 xx 的高度到 i,1≤i≤mi,1 \le i \le m ，然后左边 x−1x-1 个楼房就可以从 ii 个数字中选择递增的一段，也就是 Cix−1C_{i}^{x-1} 。右边也是 m−i+1m-i+1 个可选数字 我们可以选择一个递增的一段，也就是 Cm−i+1n−xC_{m-i+1}^{n-x} 。

同理，我们可以对 yy 进行划分

两个答案是 Cm−i+1y−n−1C_{m-i+1}^{y-n-1} , Ci2n−yC_i^{2n-y}

根据乘法原理，对于每个 ii 的方案数量就是这四个数字相乘

答案加起来就好了
ans=∑i=1m(Cix−1×Cm−i+1n−x×Cm−i+1y−n−1×Ci2n−y) ans=\sum_{i=1}^m (C_{i}^{x-1} \times C_{m-i+1}^{n-x} \times C_{m-i+1}^{y-n-1}\times C_i^{2n-y})

  • 两个在同一边

    那就好办了，那就是他们中间都是一样高的

    答案就是 Cmn×Cmn+x−yC_m^n \times C_m^{n+x-y}

但是，这道题目的核心并不是分析这个，这个小学生都能分析出来吧

我们要做的最难得就是求组合数，这个组合数非常大，我们直接求肯定会炸掉吧

即使用杨辉三角形也会复杂度爆炸吧

所以，请循其本 Cnm=n!m!(n−m)!C_n^m=\dfrac {n!} {m!(n-m)!}

我们用一个阶乘，然后利用在模意义下的逆元就好了啊，我们可以用费马小定理来求逆元吧

然后就没有然后了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long 
using namespace std;
const int maxn=200005;
const int mod=998244353;
int m,n,x,y;
int ans;
int fac[maxn],ifac[maxn];
int ksm(int a,int b)
{
	int res=1%mod;
	while(b)
	{
		if(b&1)
		res=res%mod*a%mod;
		a=a%mod*a%mod;
		b>>=1;
	}
	return res%mod;
}
int C(int m,int n)
{
	return fac[n+m-1]*ifac[n]%mod*ifac[m-1]%mod;
}
signed main()
{
	cin>>m>>n>>x>>y;
	fac[0]=1;
	for(int i=1;i<=m+n;i++)
	fac[i]=fac[i-1]*i%mod;
	ifac[m+n]=ksm(fac[m+n],mod-2);
	for(int i=m+n-1;~i;i--)
	ifac[i]=ifac[i+1]*(i+1)%mod;
	if(x<=n&&y>n)
	{
		for(int i=1;i<=m;i++)
		ans=(ans%mod+C(i,x-1)%mod*C(m-i+1,n-x)%mod*C(m-i+1,y-n-1)%mod*C(i,2*n-y)%mod+mod)%mod;		
	}
	else
	ans=C(m,n)*C(m,n+x-y)%mod;
	cout<<ans<<'\n';
	return 0;
}