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

我们考虑如何使用组合数学来做这道生成函数。你首先知道这是一个错排问题。考虑一个组合方案是

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})

。计算是容易的。

CPP

#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;
}

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

文章操作

相关推荐

评论

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