526互联

Atcoder Grand Contest 060 D - Same Descent Set

发布时间 2023-05-22 23:25:23作者: tzc_wk

先推式子。设 \(f(S)\) 表示 decent 集合恰好为 \(S\) 的排列个数，\(g(S)\) 表示 \(S\) 是 \(p\) 的 decent 集合的一个子集的排列 \(p\) 个数，\(g'(\{a_1,a_2,\cdots,a_k\})=\dfrac{n!}{a_1!(a_2-a_1)!(a_3-a_2)!\cdots(a_k-a_{k-1})!(n-a_k)!}\)，那么有：

\[\begin{aligned} ans=&\sum_{S}f(S)^2\\ =&\sum\limits_{S}(\sum\limits_{S\subseteq T_1}(-1)^{|T_1|-|S|}g(T_1))(\sum\limits_{S\subseteq T_2}(-1)^{|T_2|-|S|}g(T_2))\\ =&\sum\limits_{T_1}\sum\limits_{T_2}g(T_1)(-1)^{|T_1|}·g(T_2)(-1)^{|T_2|}·2^{|T_1\cap T_2|}\\ =&\sum\limits_{T_1}\sum\limits_{T_2}g'(T_1)(-1)^{|T_1|+1}·g'(T_2)(-1)^{|T_2|+1}·2^{n-1-|T_1\cup T_2|}\\ =&\sum\limits_{T_1}\sum\limits_{T_2}g'(T_1)(-0.5)^{|T_1|+1}·g'(T_2)(-0.5)^{|T_2|+1}·2^{n+1+|T_1\cap T_2|}\\ =&\sum\limits_{T_1}\sum\limits_{T_2}g'(T_1)(-0.5)^{|T_1|+1}·g'(T_2)(-0.5)^{|T_2|+1}·2^{n+1}(\sum\limits_{S\subseteq T_1,S\subseteq T_2}1) \end{aligned} \]

考虑最后一个式子的含义，相当于我先将 \(n\) 个元素划分为 \(p\) 个部分 \(a_1,a_2,\cdots,a_p\) 使得 \(\sum a_p=n\)，再对于每个 \(a_i\)，构造两个序列 \(b_{i,1},b_{i,2},\cdots,b_{i,q_i}\) 和 \(c_{i,1},c_{i,2},\cdots,c_{i,r_i}\)，使得 \(\sum b_{i,j}=\sum c_{i,j}=a_i\)，方案数为 \(\prod -\dfrac{1}{2(b_{i,j}!)}·\prod-\dfrac{1}{2(c_{i,j}!)}\)，我们考虑设 \(f_i\) 为将长度为 \(i\) 的部分划分为若干个小部分的系数之和，显然 \(f_i=\sum\limits_{j=0}^{i-1}f_j·(-\dfrac{1}{2(i-j)!})\)，再设 \(g_i\) 表示将长度为 \(i\) 的序列划分为若干个大部分的贡献之和，有 \(g_i=\sum\limits_{j=0}^{i-1}g_if_{i-j}^2\)，两部分都可以分治 NTT 或者多项式求逆，时间复杂度 \(O(n\log n)\) 或 \(O(n\log^2n)\)。

const int MAXN=2e5;
const int MAXP=1<<19;
const int pr=3;
const int ipr=332748118;
const int MOD=998244353;
const int INV2=MOD+1>>1;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int rev[MAXP+5];
void NTT(vector<int>&a,int len,int type){
	int lg=31-__builtin_clz(len);
	for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
	for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=2;i<=len;i<<=1){
		int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
		for(int j=0;j<len;j+=i){
			for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){
				int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
				a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
			}
		}
	}
	if(!~type){
		int iv=qpow(len,MOD-2);
		for(int i=0;i<len;i++)a[i]=1ll*a[i]*iv%MOD;
	}
}
vector<int>conv(vector<int>a,vector<int>b){
	int LEN=1;while(LEN<a.size()+b.size())LEN<<=1;
	a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);
	for(int i=0;i<LEN;i++)a[i]=1ll*a[i]*b[i]%MOD;
	NTT(a,LEN,-1);return a;
}
int n,res,fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD; 
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int f[MAXN+5],g[MAXN+5];
void calc_f(int l,int r){
	if(l==r)return;vector<int>A,B,C;int mid=l+r>>1;calc_f(l,mid);
	for(int i=l;i<=mid;i++)A.pb(f[i]);
	for(int i=0;i<=r-l;i++)B.pb(1ll*ifac[i]*(MOD-INV2)%MOD);
	C=conv(A,B);
	for(int i=mid+1;i<=r;i++)f[i]=(f[i]+C[i-l])%MOD;
	calc_f(mid+1,r);
}
void calc_g(int l,int r){
	if(l==r)return;vector<int>A,B,C;int mid=l+r>>1;calc_g(l,mid);
	for(int i=l;i<=mid;i++)A.pb(g[i]);
	for(int i=0;i<=r-l;i++)B.pb(1ll*f[i]*f[i]%MOD);
	C=conv(A,B);
	for(int i=mid+1;i<=r;i++)g[i]=(g[i]+C[i-l])%MOD;
	calc_g(mid+1,r);
}
int main(){
	scanf("%d",&n);init_fac(MAXN);f[0]=g[0]=1;calc_f(0,n);calc_g(0,n);
	printf("%d\n",1ll*g[n]*qpow(2,n+1)%MOD*fac[n]%MOD*fac[n]%MOD);
	return 0;
}