洛谷 P4931 - [MtOI2018]情侣?给我烧了!(加强版)(组合数学)
阅读原文时间:2023年07月08日阅读:3

洛谷题面传送门

A 了这道题+发这篇题解,就当过了这个七夕节吧

奇怪的过节方式又增加了

首先看到此题第一眼我们可以想到二项式反演,不过这个 \(T\) 组数据加上 \(5\times 10^6\) 的数据范围肯定是反演不动的,因此考虑怎样不反演。

我们很显然可以将求解这个问题划分成两部分:选出 \(k\)​ 对相邻的情侣并将它们的位置安排好+排列好剩下 \(n-k\)​ 对情侣。两部分显然是独立的,因此分别考虑。第一部分是是比较容易的,选出 \(k\)​ 对情侣方案数 \(\dbinom{n}{k}\)​,选出 \(k\)​ 排位置方案数 \(\dbinom{n}{k}\)​,将这 \(k\)​ 对与 \(k\)​ 排座位对应方案数 \(k!\)​,将 \(k\)​ 对情侣随意调换位置 \(2^k\)​,因此第一部分方案数就是 \(\dbinom{n}{k}^2k!2^k\)​。第二部分显然可以等效于求安排好 \(n-k\)​ 对情侣的方案数,假设这东西为 \(f_{n-k}\)​,显然这东西是要预处理的,考虑怎么预处理 \(f_n\)​。注意到这东西跟错排数长得很像但又不完全一致,因此考虑错排数的套路,我们枚举第一排是哪两个人坐在一起的,那么方案数为 \(2n·(2n-2)\)​,第二个地方要减 \(2\)​ 因为一个人不能和自己的情侣坐在一起,那么考虑这两个人的 boy/girlfriend 是否坐在一起,如果它们坐在一起那不错,这两对 couple 就消失了,剩余部分就是 \(f_{n-2}\)​,不过安排好第一排这两个人的 boy/girlfriend 还需乘上个 \(2(n-1)\)​,因为要选择一排给他们坐,他们的位置还可以交换,因此需乘个 \(2\)​。如果它们不坐一起,那么我们就把这东西当作一个限制条件,强制令它们贴贴,形成一对新的 couple,这样问题就规约为 \(f_{n-1}\)​,因此我们得到了递推式 \(f_n=2n·(2n-2)(f_{n-1}+2(n-1)f_{n-2})\),线性求一下即可。

时间复杂度 \(\mathcal O(n+T)\)

祝大家七夕节快乐

const int MAXN=5e6;
const int MOD=998244353;
int fac[MAXN+5],ifac[MAXN+5],pw2[MAXN+5],f[MAXN+5];
void init_fac(int n){
    for(int i=(fac[0]=ifac[0]=ifac[1]=pw2[0]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=n;i++) ifac[i]=1ll*ifac[i]*ifac[i-1]%MOD,fac[i]=1ll*fac[i-1]*i%MOD,pw2[i]=(pw2[i-1]<<1)%MOD;
    f[0]=1;for(int i=2;i<=n;i++) f[i]=4ll*i*(i-1)%MOD*(f[i-1]+2ll*(i-1)*f[i-2]%MOD)%MOD;
}
int binom(int x,int y){
    if(x<0||y<0||x<y) return 0;
    return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int main(){
    init_fac(MAXN);int qu;scanf("%d",&qu);
    while(qu--){
        int n,k;scanf("%d%d",&n,&k);
        printf("%d\n",1ll*binom(n,k)*binom(n,k)%MOD*pw2[k]%MOD*fac[k]%MOD*f[n-k]%MOD);
    }
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章