题解 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个里总得选一个，女的就有一个不能选，左右交换也是可以的，所以是2*k*(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;} ```