自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 22:40:31，当前版本为作者最后更新于2022-08-08 21:28:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前几个 Subtask 部分可以使用暴力、动态规划与矩阵快速幂优化动态规划解决，在此不一一阐述。

对于这道题，我们会发现一个特性，就是最多只能使用 $1\times2$ 的竖着的长方形以及一些横着的长方形来摆放。

阅读提示，以下定义 $\dbinom{i}{j}=0$ 当 $i<j$ 或 $i<0$ 或 $j<0$。

先考虑一个简单版本的问题，请问使用 $a$ 个长方形，只允许横着的，铺满 $2\times b$ 的方格的方案数。

考虑我们给上面一半放置 $i$ 个横着的长方形，那么下面一半就需要放 $a-i$ 长方形，这时，我们可以使用插板法，上面要放 $i$ 个长方形，且有 $b$ 个格子，那么答案就是 $\dbinom{b-1}{i-1}$，同理下面是 $\dbinom{b-i}{a-i-1}$。总方案数为 $\sum_{i=0}^{a} \dbinom{b-1}{i-1}\times \dbinom{b-1}{a-i-1}$。这个式子的实际含义可以看成从 $2b-2$ 个位置中，选取 $a-2$ 个板子，然而上面这种计算方法其实就是相当于枚举在前 $b-1$ 个位置中选出若干个，剩下来在后 $b-1$ 个位置中选择，我们也自然得知：$\sum_{i=0}^{a} \dbinom{b-1}{i-1}\times \dbinom{b-1}{a-i-1}=\dbinom{2b-2}{a-2}$，通过组合意义的方式可以证明（也不是没有纯组合证明，可以自行搜索）。

解决了这个小问题，我们可以来谈谈大体的思路。直接计算这个问题不好算，我们考虑先用 $j$ 个竖着的 $1\times2$ 的长方形，并把原来一整段的 $2\times n$ 大小的长方形分成了 $i$ 个 $2\times a_l$ 的独立的小段长方形，然后求其方案数，最终统一计算即可。

那么，现在我们的问题转换成了用 $j$ 个竖着的 $1\times2$ 的长方形，并把原来一整段的 $2\times n$ 大小的长方形分成了 $i$ 个 $2\times a_l$ 的独立的小段长方形的情况的方案数，

首先，我们会考虑将使用的 $j$ 个竖着的长方形时，将这 $j$ 个长方形分在 $i-1$ 个必须要有的段落之间的空格内以及在长方形左右两端的地方。也就是说，想要使得 $d_0+d_1+d_2+...+d_{i-1}+d_i=j,0\leq d_0,d_i,1\leq d_1,d_2,d_3...d_{i-1}$。这个问题又转化成了一个经典的插板问题，方案数是 $\dbinom{j+1}i$。

其次，我们假设每段分出来的距离是 $a_1,a_2,...,a_i$，那么我们还要把剩下的 $n-j$ 个位置分给这 $i$ 段。显然，每一段的长度都要求是正整数。那么方案数就是 $\dbinom{n-j-1}{i-1}$。

最后，我们还要考虑把剩下来的 $k-j$ 个长方形分到每段 $a_i$ 中，其实就是求：

$$\sum_{\sum_{l=1}^i b_l=k-j} \prod_{l=1}^i \dbinom{2a_l-2}{b_l-2} $$

很明显，这个式子可以表示成从 $\sum 2a_l-2$ 个位置中，选取 $\sum b_l-2$ 的所有方法，原式的意义就是先枚举每个段落选几个，再把所有方案相加，本质上就是求整个序列位置数中选取板子数。那么其实就是 $\dbinom{2n-2j-2i}{k-j-2i}$。

然后你把搞的式子交上去，你会获得 $10$ 分的好成绩，你需要知道自己为啥挂了。显然，我们没有考虑当 $n=k$ 时，你其实只需要在 $ans$ 上特判一下即可。

所以最终公式为：

$$\sum_{i=1}^k\sum_{j=0}^k\dbinom{2n-2j-2i}{k-j-2i}\times \dbinom{j+1}i\times \dbinom{n-j-1}{i-1}+[n=k] $$

#include <bits/stdc++.h>
using namespace std;
int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=((long long)ans*a)%mod;
		a=((long long)a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[40000005],inv[40000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=40000000;i++){
		fac[i]=((long long)fac[i-1]*i)%mod;
	}
	inv[40000000]=qp(fac[40000000],mod-2);
	for(int i=39999999;i>=0;i--){
		inv[i]=((long long)inv[i+1]*(i+1))%mod;
	}
}
long long C(int i,int j){
	return (long long)((long long)inv[j]*inv[i-j]%mod)*fac[i]%mod;
}
signed main(){
	init();
	int n,k;
	cin>>n>>k;
	int ans=0;
	for(int i=1;i<=k;i++){
		for(int j=0;j<=k&&k-j-2*i>=0;j++){
		    if(2*(n-i-j)<0||k-j-2*i<0||n-j-1<0||2*(n-i-j)<k-j-2*i||j+1<i||n-j-1<i-1) continue;
			ans=(ans+((long long)(C(2*(n-i-j),k-j-2*i)*C(j+1,i)%mod)*(long long)C(n-j-1,i-1)%mod))%mod;
		}
	}
	cout<<(ans+(n==k))%mod;
}