【3】题解：P4931 [MtOI2018] 情侣？给我烧了！（加强版）【组合数学】

ExFish · 2025-11-20 14:06:09 · 题解

我们考虑如何使用组合数学来做这道生成函数。你首先知道这是一个错排问题。考虑一个组合方案是 f_{i,j} 为有 i 对情侣 j 对在一起的方案数。我们显然有一个排列为 \binom{i}{j} 为选择 j 个对在一起。然后我们考虑这些人的顺序，有 A_{i}^j 的方案。然后左右互换是 2^j，总方案数是 f_{i,j}=\binom{i}{j}\times A_i^j\times 2^j。

然后其他的情况就需要考虑情侣 i-j 对不坐在一起的情况。设 g_k 为 k 对情侣不在一起的方案数。首先是男通 / 百合就是 k(k-1)。然后非情侣的就是男选一女不能选显然就是 2k(k-1)。然后他们原始的配偶就需要递归进去为 g_{k-2} 与 g_{k-1}。综合这里可以计算出来 g_k=4k(k-1)(g_{k-1}+2(k-1)g_{k-2})。计算是容易的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e6+10;
const ll P=998244353;
ll qp(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=(a*a)%P)
        if(b&1) res=(res*a)%P;
    return res;
}
ll fac[N],fiv[N],f[N],p2[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n=5e6,k,T;
    fac[0]=1, p2[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%P,
        p2[i]=p2[i-1]*2%P;
    fiv[n]=qp(fac[n],P-2);
    for(int i=n;i>=1;i--)
        fiv[i-1]=fiv[i]*i%P;
    f[0]=1,f[1]=0;
    for(int i=2;i<=n;i++)   
        f[i]=(f[i-1]+f[i-2]*2*(i-1)%P)%P*4%P*i%P*(i-1)%P;
    cin>>T;
    while(T--){
        cin>>n>>k;  
        cout<<fac[n]*fiv[n-k]%P*fac[n]%P*fiv[k]%P*fiv[n-k]%P*p2[k]%P*f[n-k]%P<<"\n";
    }
    return 0;
}