题解 P4931 【情侣？给我烧了！（加强版）】

· · 题解

一道披着黑皮的蓝...

sb组合数学，但我不会qwq

设f[i,j]为i对情侣，恰有j对在一起的方案数。

显然，对于这j对在一起的，我们要先从i排里找出j排，有C(i,j)种方法；再把这些人排个顺序坐,有P(i,j)种方法，考虑左右交换：有2^j种方案。

那么问题来了，对于这i-j对不坐在一起的怎么办？我们可以递推求解，设g[k]为k对情侣都不坐在一起的方案数。那么我们分类讨论：

1、先选择一对基佬

显然，方案数为C(k,2)2,乘2还是因为可以交换。化简可得k(k-1)

2、先选择一对妹子

显然同上。

3、选择一男一女，但不是情侣

男的k个里总得选一个，女的就有一个不能选，左右交换也是可以的，所以是2k(k-1)

选完后，考虑他们的配偶（总不能晾着不管

1、坐在一起，那么可以在k-1排里选一排，左右顺序可变，问题规模减少2； 2、不坐在一起，问题规模减少一。 乘上前面的，即可得： g[k]=4k(k-1)(g[k-1]+2(k-1)g[k-2])

总方案数f[n,k]=C(n,k)P(n,k)2^k*g[k]。预处理阶乘逆元2的幂以及g数组，就可以O(1)回答啦~

附AC代码（压行什么的，才没有呢

#include<bits/stdc++.h>
const int M=998244353,N=5000005;
long long n,k,t,fac[N]={1},rev[N],g[N]={1,0},p[N]={1};
long long power(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)res=res*a%M;
        b>>=1;
        a=a*a%M;}
    return res;}
int main(){
    for(int i=1;i<=N;++i)fac[i]=fac[i-1]*i%M;
    rev[N]=power(fac[N],M-2);
    for(int i=N;i;--i )rev[i-1]=rev[i]*i%M;
    for(int i=2;i<=N;++i)g[i]=(g[i-1]+g[i-2]*2*(i-1))%M*4*i%M*(i-1)%M;
    for(int i=1;i<=N;++i)p[i]=p[i-1]*2%M;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        printf("%lld\n",fac[n]*rev[n-k]%M*fac[n]%M*rev[k]%M*rev[n-k]%M*p[k]%M*g[n-k]%M);}
    return 0;}