专栏文章

题解：AT_agc064_f [AGC064F] No Permutations

llittlez_meow
AT_agc064_f题解参与者 3已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miqqcqet
此快照首次捕获于
2025/12/04 09:01
3 个月前
此快照最后确认于
2025/12/04 09:01
3 个月前
查看原文
upd on 2025.1.1：式子出现了一些打错的地方。

思路

搬运一下官方题解做法。
直接做肯定没法做，考虑容斥。
记所有长度为 nn 的区间的集合 R={[1,n+1),[2,n+2),⋯ ,[2n+1,3n+1)}R=\{[1,n+1),[2,n+2),\cdots,[2n+1,3n+1)\}，设 S⊆RS\subseteq R，定义 f(S)f(S) 表示 (−1)∣S∣(-1)^{|S|} 乘上满足“SS 中任意区间都是 1∼n1\sim n 的排列”的方案数。下面如无特殊说明，区间全部左闭右开。
则答案为 ∑S⊆Rf(S)\sum\limits_{S\subseteq R}f(S)。
当 S=∅S=\varnothing 时，f(S)=(3n)!(3!)nf(S)=\dfrac{(3n)!}{(3!)^n}，也就是把相同值元素看作不同再除以每种方案重复算的次数。下面只讨论 S≠∅S\neq\varnothing 的情况。
定义两个区间 [l,l+n),[r,r+n)[l,l+n),[r,r+n) 相交当且仅当 ∣l−r∣≤n|l-r|\le n，注意 ∣l−r∣=n|l-r|=n 的时候也是相交。定义一个连通块是一个区间的集合 TT，满足对于其中任意两个区间 a,ba,b，都存在一个区间的序列 a=r1,r2,⋯ ,rk=ba=r_1,r_2,\cdots,r_k=b，其中 ri(2≤i≤k)r_i(2\le i\le k) 与 ri−1r_{i-1} 相交。此时称 TT 是连通的，其长度为区间 ⋃x∈Tx\bigcup_{x\in T} x 的长度，记为 len⁡(T)\operatorname{len}(T)。
直接计算所有 S⊆R,S≠∅S\subseteq R,S\neq\varnothing（下记为 S∈2R∖{∅}S\in 2^R\setminus\{\varnothing\}，即 SS 是 RR 的幂集的元素）的贡献不好算，我们把 2R∖{∅}2^R\setminus\{\varnothing\} 划分成两个集合分别计算贡献。如无特殊说明，下面默认 S∈2R∖{∅}S\in 2^R\setminus\{\varnothing\}，全集是 2R∖{∅}2^R\setminus\{\varnothing\}。
设 P⊆2RP\subseteq 2^R 是满足以下条件的 SS 的集合：存在一个区间 x∈Sx\in S，满足对于所有 y∈Sy\in S，x,yx,y 相交。再设 QQ 是 PP 的补集。
那么下面就剩下了两个问题：计算 ∑S∈Pf(S)\sum\limits_{S\in P}f(S) 和 ∑S∈Qf(S)\sum\limits_{S\in Q}f(S)。

计算 ∑S∈Pf(S)\sum\limits_{S\in P}f(S)

设 len⁡(S)=n+L\operatorname{len}(S)=n+L，SS 中区间左端点分别为 l0<l1<⋯<lkl_0<l_1<\cdots<l_k，不难发现 lk=l0+Ll_k=l_0+L，则排列的方案数有以下几部分：
  • [l0,l0+n)[l_0,l_0+n) 是 1∼n1\sim n 的排列，方案数 n!n!。
  • [l0+n,l1+n)[l_0+n,l_1+n) 是区间 [l0,l1)[l_0,l_1) 的排列，方案数 (l1−l0)!(l_1-l_0)!。
  • [l1+n,l2+n)[l_1+n,l_2+n) 是区间 [l1,l2)[l_1,l_2) 的排列，方案数 (l2−l1)!(l_2-l_1)!。
  • 依此类推，[lk−1+n,lk+n)[l_{k-1}+n,l_k+n) 是区间 [lk−1,lk)[l_{k-1},l_k) 的排列，方案数 (lk−lk−1)!(l_k-l_{k-1})!。
  • 不被任何区间包含的 2n−L2n-L 个元素，方案数 ρ(2n−L)=(2n−L)!2max⁡(n−L,0)\rho(2n-L)=\dfrac{(2n-L)!}{2^{\max(n-L,0)}}。这是因为总共有 (2n−L)!(2n-L)! 种方案，其中有 max⁡(n−L,0)\max(n-L,0) 对相同元素会算重。
全部乘起来，把容斥系数拆到求积号里面，有 f(S)=−n!ρ(2n−L)∏i=1k(−(li−li−1)!)f(S)=-n!\rho(2n-L)\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。
枚举 LL 求和得到 ∑S∈Pf(S)=−n!∑L=02nρ(2n−L)∑S∈P,len⁡(S)=n+L∏i=1k(−(li−li−1)!)\sum\limits_{S\in P}f(S)=-n!\sum\limits_{L=0}^{2n}\rho(2n-L)\sum\limits_{S\in P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。
问题转化为求 ∑S∈P,len⁡(S)=n+L∏i=1k(−(li−li−1)!)\sum\limits_{S\in P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。
观察发现 li−li−1l_i-l_{i-1} 是一组 LL 的拆分，可以用生成函数描述。但是生成函数只是无脑加起来，并不能满足 S∈PS\in P 的限制。所以我们考虑放宽限制。
设 P′P' 表示连通的 SS 的集合。容易得到 P⊆P′P\subseteq P'。因此要求 ∑S∈P′,len⁡(S)=n+L∏i=1k(−(li−li−1)!)−∑S∈P′∖P,len⁡(S)=n+L∏i=1k(−(li−li−1)!)\sum\limits_{S\in P',\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)-\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。
先来解决式子的第一项。正如刚刚说的，求积号里是一个拆分，可以用生成函数描述。
设 w(L)=[xL]11+∑i=1ni!xiw(L)=[x^L]\dfrac{1}{1+\sum\limits_{i=1}^n i!x^i}，则 ∑S∈P′,len⁡(S)=n+L∏i=1k(−(li−li−1)!)=(2n−L+1)w(L)\sum\limits_{S\in P',\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)=(2n-L+1)w(L)。这里 2n−L+12n-L+1 是 l0l_0 的选法。
求 w(1)∼w(2L)w(1)\sim w(2L) 可以用多项式求逆 O(nlog⁡n)O(n\log n) 求出来。
接下来就是本题最难的部分，求 ∑S∈P′∖P,len⁡(S)=n+L∏i=1k(−(li−li−1)!)\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)。
我们先考虑 S∈P′∖PS\in P'\setminus P 长什么样子。设 SS 最左边的区间是 [u,u+n)[u,u+n)，最右边是 [v,v+n)[v,v+n)。你发现，由于每个区间长为 nn，因此任意一个 SS 中区间都会和 [u,u+n),[v,v+n)[u,u+n),[v,v+n) 中恰好一个相交。这是因为如果和两个相交就属于 PP 了，和两个都不相交长度就不可能到达 nn。
于是，设和 [u,u+n)[u,u+n) 相交的区间的集合是 UU，和 [v,v+n)[v,v+n) 相交的区间的集合是 VV。显然，U,VU,V 都是连通的。UU 的长度是 n+xn+x，区间左端点是 u=u0<u1<⋯<up=u+xu=u_0<u_1<\cdots<u_p=u+x；VV 的长度是 n+yn+y，区间左端点是 v=v0<v1<⋯<vq=v+xv=v_0<v_1<\cdots<v_q=v+x；zz 是 U,VU,V 的交的长度，即 z=(up+n)−v0z=(u_p+n)-v_0。则，x+y−z+n=L,x∈[0,n),y∈[0,n),z∈(0,min⁡{x,y})x+y-z+n=L,x\in[0,n),y\in[0,n),z\in(0,\min\{x,y\})。不妨令 (x,y,z)(x,y,z) 的三元组的集合是 AA，即 A={(x,y,z)∈Z3∣x∈[0,n),y∈[0,n),z∈[0,min⁡{x,y})}A=\{(x,y,z)\in\mathbb{Z}^3|x\in[0,n),y\in[0,n),z\in[0,\min\{x,y\})\}。三元组中 zz 是最小的。
所以有 ∑S∈P′∖P,len⁡(S)=n+L∏i=1k(−(li−li−1)!)=∑S∈P′∖P,len⁡(S)=n+L(v0−up)!∏i=1p(−(ui−ui−1)!)∏i=1q(−(vi−vi−1)!)\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}\prod\limits_{i=1}^k(-(l_i-l_{i-1})!)=\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}(v_0-u_p)!\prod\limits_{i=1}^p(-(u_i-u_{i-1})!)\prod\limits_{i=1}^q(-(v_i-v_{i-1})!)。这里前面没有负号是因为 U,VU,V 的负号消掉了。
类似于上面的讨论，我们有该式等于 ∑S∈P′∖P,len⁡(S)=n+L(n−z)!w(x)w(y)\sum\limits_{S\in P'\setminus P,\operatorname{len}(S)=n+L}(n-z)!w(x)w(y)。
枚举 SS 变为枚举 (x,y,z)(x,y,z)，得到该式等于 (2n−L+1)∑(x,y,z)∈A,x+y−z+n=L(n−z)!w(x)w(y)(2n-L+1)\sum\limits_{(x,y,z)\in A,x+y-z+n=L}(n-z)!w(x)w(y)。2n−L+12n-L+1 是 l0l_0 的选法。
不妨设 BL=−∑(x,y,z)∈A,x+y−z=L−n(n−z)!w(x)w(y)B_L=-\sum\limits_{(x,y,z)\in A,x+y-z=L-n}(n-z)!w(x)w(y)。我们需要快速求出 B0∼BnB_0\sim B_{n}。这里前面的负号是为了把之前的式子前面的减变成加。
考虑分治。设 solve(l,r) 表示将满足 x,y,z∈[l,r)x,y,z\in[l,r) 的所有 (x,y,z)∈A(x,y,z)\in A 的贡献加进 Bx+y−zB_{x+y-z}，再设 m=⌊l+r2⌋m=\lfloor\dfrac{l+r}{2}\rfloor。一共有三种贡献：
  • x,y,z<mx,y,z<m 或 x,y,z≥mx,y,z\ge m 时，可以递归下去。
  • z<m≤min⁡{x,y}z<m\le\min\{x,y\} 时，x,yx,y 可以任取 [m,r)[m,r) 的值，与 zz 无关。我们要对于每个 LL 求出 ∑x+y−z=L−n[z∈[l,m)][x∈[m,r)][y∈[m,r)](n−z)!w(x)w(y)\sum\limits_{x+y-z=L-n}[z\in[l,m)][x\in[m,r)][y\in[m,r)](n-z)!w(x)w(y)。可以先把 x,yx,y 做和卷积，再把结果和 zz 做差卷积，用 NTT 做到 O((r−l)log⁡(r−l))O((r-l)\log(r-l))。
  • z≤min⁡{x,y}<m≤max⁡{x,y}z\le\min\{x,y\}<m\le\max\{x,y\} 时，由于 x,yx,y 是对称的，不妨令 x<yx<y ，答案乘 22 即可，这是因为 x=yx=y 必不可能满足 min⁡{x,y}<m≤max⁡{x,y}\min\{x,y\}<m\le\max\{x,y\}。因此有 z≤x<m≤yz\le x<m\le y，先把 x,zx,z 做差卷积，再和 yy 做和卷积即可 O((r−l)log⁡(r−l))O((r-l)\log(r-l))。
时间复杂度 O(nlog⁡2n)O(n\log^2 n)。

计算 ∑S∈Qf(S)\sum\limits_{S\in Q}f(S)

类似于上面的讨论，设 SS 最左边的区间是 [u,u+n)[u,u+n)，最右边是 [v,v+n)[v,v+n)，任意一个 SS 中区间都会和 [u,u+n),[v,v+n)[u,u+n),[v,v+n) 中恰好一个相交。设和 [u,u+n)[u,u+n) 相交的区间的集合是 UU，和 [v,v+n)[v,v+n) 相交的区间的集合是 VV。显然，U,VU,V 都是连通的。UU 的长度是 n+xn+x，区间左端点是 u=u0<u1<⋯<up=u+xu=u_0<u_1<\cdots<u_p=u+x；VV 的长度是 n+yn+y，区间左端点是 v=v0<v1<⋯<vq=v+xv=v_0<v_1<\cdots<v_q=v+x；zz 是 U,VU,V 的距离，即 z=v−u−nz=v-u-n。
排列的方案数有以下几部分：
  • 不被 [u,u+n),[v,v+n)[u,u+n),[v,v+n) 包含的部分，一共 n!n! 种方案。
  • [u,u+n)[u,u+n) 包含的部分：
    • [up,u+n)[u_p,u+n) 是不在 [u+n,u+n+x)[u+n,u+n+x) 元素的排列，方案数 (n−x)!(n-x)!。
    • [up−1,up)[u_{p-1},u_p) 是 [up−1+n,up+n)[u_{p-1}+n,u_p+n) 元素的排列，方案数 (up−up−1)!(u_p-u_{p-1})!。
    • 依此类推，[u0,u1)[u_0,u_1) 是区间 [u0+n,u1+n)[u_0+n,u_1+n) 的排列，方案数 (u1−u0)!(u_1-u_0)!。
  • [v,v+n)[v,v+n) 包含的部分，类似地，方案数 (n−y)!∏i=1q(vi−vi−1)!(n-y)!\prod\limits_{i=1}^q(v_i-v_{i-1})!。
拆一下容斥系数，有 f(S)=n!(n−x)!(n−y)!∏i=1p(−(ui−ui−1)!)∏j=1q(−(vj−vj−1)!)f(S)=n!(n-x)!(n-y)!\prod\limits_{i=1}^p(-(u_i-u_{i-1})!)\prod\limits_{j=1}^q(-(v_j-v_{j-1})!)。
枚举 SS 变成枚举 (x,y,z)(x,y,z)，结合 QQ 的定义，我们有 ∑S∈Qf(S)=n!∑z=1n(n−z+1)∑x=0z−1∑y=0z−1w(x)w(y)(n−x)!(n−y)!\sum\limits_{S\in Q}f(S)=n!\sum\limits_{z=1}^n(n-z+1)\sum\limits_{x=0}^{z-1}\sum\limits_{y=0}^{z-1}w(x)w(y)(n-x)!(n-y)!。
化简即为 ∑S∈Qf(S)=n!∑z=1n(n−z+1)(∑i=0z−1w(i)(n−i)!)2\sum\limits_{S\in Q}f(S)=n!\sum\limits_{z=1}^n(n-z+1)\left(\sum\limits_{i=0}^{z-1}w(i)(n-i)!\right)^2。n−z+1n-z+1 是选择 u0u_0。
可以前缀和优化做到 O(n)O(n) 计算。
综上，我们以 O(nlog⁡2n)O(n\log^2 n) 的时间复杂度解决了这个问题。

代码

CPP
#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define vi vector<int>
using namespace std;
const int MAXN=1<<20,MOD=998244353,INV2=499122177,INV6=166374059,G=3;
inline ll qpow(ll base,int expo){
	ll res(1);
	while(expo){
		(expo&1)&&(res=res*base%MOD);
		base=base*base%MOD,expo>>=1;
	}
	return res;
}
const int INVG=qpow(G,MOD-2);
int gpow[21],invgpow[21];
inline void calc(){
	F(i,1,20) gpow[i]=qpow(G,(MOD-1)>>i),invgpow[i]=qpow(INVG,(MOD-1)>>i);
	return;
}
inline void meow(int&t){
	t<0&&(t+=MOD);
	t>=MOD&&(t-=MOD);
	return;
}
int rev[MAXN];
inline void NTT(int*poly,int len,bool inv){
	F(i,0,len-1) (i<rev[i])&&(swap(poly[i],poly[rev[i]]),1);
	static ll g[MAXN];
	g[0]=1;
	for(int i(1),expo(1);i<len;i<<=1,++expo){
		ll omega=inv?invgpow[expo]:gpow[expo];
		F(j,1,i-1) g[j]=g[j-1]*omega%MOD;
		for(int j(0);j<len;j+=(i<<1)) F(k,0,i-1){
			int&x(poly[j|k]),&y(poly[i|j|k]);
			ll qwq(g[k]*y%MOD);
			y=x-qwq;
			y<0&&(y+=MOD);
			x+=qwq;
			x>=MOD&&(x-=MOD);
		}
	}
	if(inv){
		ll invl=qpow(len,MOD-2);
		F(i,0,len-1) poly[i]=poly[i]*invl%MOD;
	}
	return;
}
inline void build_rev(int n){
	F(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
	return;
}
struct poly{
	int num[MAXN]={};
	int len=0;
	
	inline void resize(const int a){
		for(;len>a;--len) num[len]=0;
		len=a;
		if(len<0) len=0;
		return;
	}
	inline poly operator+(const poly a)const{
		poly res;
		res.len=max(a.len,len);
		F(i,0,res.len) res.num[i]=num[i]+a.num[i],meow(res.num[i]);
		return res;
	}
	inline poly operator+(const int a)const{
		poly res=*this;
		int&qwq(res.num[0]);
		qwq+=a;
		meow(qwq);
		return res;
	}
	inline poly operator-(const poly a)const{
		return a*(-1)+*this;
	}
	inline poly operator-(const int a)const{
		return *this+(-a);
	}
	inline poly operator*(const poly a)const{
		poly x,y=*this;
		if(a.len*1ll*len<=1e5){
			x.len=a.len+len;
			F(i,0,len) F(j,0,a.len){
				int&qwq(x.num[i+j]);
				qwq=(qwq+a.num[j]*1ll*num[i])%MOD;
			}
			return x;
		}
		x=a;
		int expo=max(__lg(((len+a.len+1)<<1)+1)+1,1),l=1<<expo;
		build_rev(l);
		NTT(x.num,l,0);
		NTT(y.num,l,0);
		F(i,0,l-1) x.num[i]=1ll*x.num[i]*y.num[i]%MOD;
		NTT(x.num,l,1);
		x.resize(len+a.len);
		return x;
	}
	inline poly operator*(const int a)const{
		poly res=*this;
		F(i,0,len){
			int&qwq(res.num[i]);
			qwq=a*1ll*qwq%MOD;
			meow(qwq);
		}
		return res;
	}
	inline poly inv(){
		poly res;
		res.num[0]=qpow(num[0],MOD-2);
		for(int l(2),expo(1);l<(len<<1);l<<=1,++expo){
			int tmp[MAXN]={};
			F(i,0,(l<<1)-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<expo);
			memcpy(tmp,num,sizeof(int)*l);
			NTT(tmp,l<<1,0);
			NTT(res.num,l<<1,0);
			F(i,0,(l<<1)-1){
				int&qwq(res.num[i]),t(2-1ll*qwq*tmp[i]%MOD);
				meow(t);
				qwq=1ll*qwq*t%MOD;
			}
			NTT(res.num,l<<1,1);
			F(i,l,(l<<1)-1) res.num[i]=0;
		}
		res.resize(len);
		return res;
	}
};
int px[MAXN],py[MAXN];
inline vi mul(const vi&x,const vi&y){
	int n=x.size()+y.size()-1;
	n=1<<(__lg(n)+1);
	build_rev(n);
	F(i,0,x.size()-1) px[i]=x[i];
	F(i,x.size(),n-1) px[i]=0;
	F(i,0,y.size()-1) py[i]=y[i];
	F(i,y.size(),n-1) py[i]=0;
	NTT(px,n,0),NTT(py,n,0);
	F(i,0,n-1) px[i]=px[i]*1ll*py[i]%MOD;
	NTT(px,n,1);
	vi res(x.size()+y.size()-1);
	F(i,0,res.size()-1) res[i]=px[i];
	return res;
}
int n;
ll fact[MAXN],B[MAXN];
poly w;
inline ll rho(int L){
	return fact[2*n-L]*qpow(INV2,max(n-L,0))%MOD;
}
inline void m_le_xy(int l,int m,int r){
	vector<int>x(r-l+1),y(r-l+1);
	F(i,m,r-1) (x[i-l]+=w.num[i])>=MOD&&(x[i-l]-=MOD);
	F(i,l,m-1) y[r-i]=fact[n-i];
	x=mul(x,x);
	x=mul(x,y);
	F(i,max(r-2*l,0),x.size()-1){
		int qwq=i-r+l*2;
		if(qwq>n) break;
		(B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
	}
	return;
}
inline void x_le_m_le_y(int l,int m,int r){
	vector<int>x(r-l+1),y(r-l+1);
	F(i,l,m-1) (x[i-l]+=w.num[i])>=MOD&&(x[i-l]-=MOD);
	F(i,l,m-1) y[r-i]=fact[n-i];
	x=mul(x,y);
	F(i,0,min(int(x.size()-1),r-l)) x[i]=0;
	F(i,0,r-l) y[i]=0;
	F(i,m,r-1) y[i-l]=w.num[i];
	x=mul(x,y);
	F(i,max(r-2*l,0),x.size()-1){
		int qwq=i-r+l*2;
		if(qwq>n) break;
		(B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
		(B[qwq]+=x[i])>=MOD&&(B[qwq]-=MOD);
	}
	return;
}
void solve(int l,int r){
	if(r-l<=1) return;
	int m=(l+r)>>1;
	solve(l,m),solve(m,r);
	m_le_xy(l,m,r);
	x_le_m_le_y(l,m,r);
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	calc();
	cin>>n;
	fact[0]=1;
	F(i,1,3*n) fact[i]=fact[i-1]*i%MOD;
	F(i,0,n) w.num[i]=fact[i];
	w.len=2*n+1;
	w=w.inv();
	int ans=fact[3*n]*qpow(INV6,n)%MOD;
	F(L,0,2*n) ans=(ans+rho(L)*(MOD-fact[n])%MOD*(2*n-L+1)%MOD*w.num[L])%MOD;//S in P'
	solve(0,n);
	F(L,n,2*n) ans=(ans+rho(L)*(MOD-fact[n])%MOD*(2*n-L+1)%MOD*B[L-n])%MOD;//S in P'\P
	ll sum=0;
	F(z,1,n){//S in Q
		sum=(sum+w.num[z-1]*fact[n-z+1])%MOD;
		ans=(ans+fact[n]*(n-z+1)%MOD*sum%MOD*sum)%MOD;
	}
	cout<<ans;
	return 0;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...