KDOI R2 B 题解

· · 题解

前几个 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;
}