[Luogu4921]情侣？给我烧了！[错位排列]

题意

分析

对于每一个询问 \(k\) ，记 \(g(x)\) 表示 \(x\) 对情侣都错开的方案总数，那么答案可以写成如下形式：

\[{ans}_k= \binom{n}{k}\times A_n^k\times 2^k\times g(n-k)
\]

考虑如何求 \(g(x)\) (一个错位排列)。
考虑第一排，一共有三种情况：两男两女或者一男一女(不配对)。
- 两男：顺次选出两男的方案数为 \(x(x-1)\) ,然后考虑他们的配偶在之后的配对情况：
  - 如果强制不配对，那么把她们看成一对情侣来保证之后的过程中不配对(gay里gay气)，即 \(g(x-1)\) 。
  - 如果强制配对，那么在剩下的 \(x-1\) 排中选择一排，两人顺序可以交换，转移为 \(2(x-1)\times g(x-2)\)。
- 两女：方案数显然和两男的情况相同。
- 一男一女：枚举一男一女，可以交换顺序的方案数为 \(x(x-1)\) ，转移其实是一样的，
所以我们得到：\(g(x)=4x(x-1)\times[g(x-1)+2(x-1)\times g(x-2)]\) 。
单次处理 \(g\) 复杂度 \(O(n)\) ，每次回答枚举 \(k\) 复杂度 \(O(n)\) ，总时间复杂度为 \(O(n)\) 。

代码

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;++i)

#define pb push_back

typedef long long LL;

inline int gi(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch))	{if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

	return x*f;

}

template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}

template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}

const int N=2004,mod=998244353;

int T,n;

LL fac[N],inv[N],invfac[N],bin[N],g[N];

void add(LL &a,LL b){a+=b;if(a>=mod) a-=mod;}

LL Pow(LL a,LL b){

	LL res=1ll;

	for(;b;b>>+1,a=a*a%mod) if(b&1) res=res*a%mod;

	return res;

}

LL C(int n,int m){

	return fac[n]*invfac[n-m]%mod*invfac[m]%mod;

}

int main(){

	fac[0]=invfac[0]=inv[1]=bin[0]=1;

	rep(i,1,N-1){

		if(i^1) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

		fac[i]=fac[i-1]*i%mod;

		invfac[i]=invfac[i-1]*inv[i]%mod;

		bin[i]=bin[i-1]*2%mod;

	}

	g[0]=1,g[1]=0;

	rep(n,2,1000) g[n]=4ll*n*(n-1)%mod*(g[n-1]+2*(n-1)*g[n-2])%mod;

	T=gi();

	while(T--){

		n=gi();

		rep(k,0,n) printf("%lld\n",C(n,k)*C(n,k)%mod*fac[k]%mod*bin[k]%mod*g[n-k]%mod);

	}

	return 0;

}

巴特西

[Luogu4921]情侣？给我烧了！[错位排列]

题意

分析

代码

最新文章

热门文章