专栏文章

「题单题解」数数入门

CCoffee_zzz/xin
算法·理论参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minn07oq
此快照首次捕获于
2025/12/02 05:04
3 个月前
此快照最后确认于
2025/12/02 05:04
3 个月前
查看原文

P1758 [NOI2009] 管道取珠

题解
有一个经典的 trick 是，可以将每个东西出现次数的平方转化为选择两个相同东西的方案数。对于此题，即为将 ∑ai2\sum {a_i}^2 转化为选择两个相同的输出序列的方案数。
考虑 dp：设 fi,j,kf_{i,j,k} 表示，选择两个长度为 ii 的相同的输出序列，第一个输出序列由上管道中的 jj 个球和下管道中的 i−ji-j 个球构成，第二个输出序列由上管道中的 kk 个球和下管道中的 i−ki-k 个球构成的方案数。转移时枚举两个输出序列的下一位分别选择哪个管道即可。
对第一维做滚动优化，时间复杂度 O(n3)\mathcal O(n^3)，空间复杂度 O(n2)\mathcal O(n^2)。
代码C
const int N=505,mod=1024523;
int n,m,f[2][N][N];
string s,t;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n>>m>>s>>t;
	f[0][0][0]=1;
	for(int i=0;i<n+m;i++){
		int x=i&1,y=(i&1)^1;
		for(int j=0;j<=min(n,i);j++){
			for(int k=0;k<=min(n,i);k++){
				if(j<n&&k<n&&s[j]==s[k]) add(f[y][j+1][k+1],f[x][j][k]);
				if(j<n&&i-k<m&&s[j]==t[i-k]) add(f[y][j+1][k],f[x][j][k]);
				if(i-j<m&&k<n&&t[i-j]==s[k]) add(f[y][j][k+1],f[x][j][k]);
				if(i-j<m&&i-k<m&&t[i-j]==t[i-k]) add(f[y][j][k],f[x][j][k]);
			}
		}
		memset(f[x],0,sizeof f[x]);
	}
	cout<<f[(n+m)&1][n][n];
}

ABC295E Kth Number

题解
设 aa 中 00 的个数为 cc。题目需要我们求出 aka_k 的期望值，转化一下可以变成：求对于所有 mcm^c 种序列 aa，aka_k 之和，即：
∑aak\sum_a a_k
求第 kk 小的数不好求，于是考虑把 aka_k 的贡献拆到每一个 1≤v≤ak1 \le v \le a_k 的 vv 上，式子变成：
∑v=1m∑a[v≤ak]\sum_{v=1}^m\sum_a [v \le a_k]
于是我们可以枚举 vv，计算有多少种 aa 满足 v≤akv \le a_k。
设 aa 中小于 vv 的不为 00 的数有 xx 个，枚举一下再添加多少个小于 vv 的数，那么答案即为：
∑i=0k−x−1(ci)⋅(v−1)i⋅(m−v+1)c−i\sum_{i=0}^{k-x-1} {c \choose i} \cdot (v-1)^i\cdot (m-v+1)^{c-i}
注意特判 c<ic \lt i 的情况。
时间复杂度 O(n2)\mathcal O(n^2)。
代码C
const int N=2005,mod=998244353;
int n,m,k,a[N],pw[N][N],c,fac[N],infac[N],ans;
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
int C(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==0) c++;
	}
	for(int i=0;i<N;i++){
		pw[i][0]=1;
		for(int j=1;j<N;j++) pw[i][j]=1ll*pw[i][j-1]*i%mod;
	}
	fac[0]=1,infac[0]=1;
	for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%mod,infac[i]=ksm(fac[i],mod-2);
	for(int v=1;v<=m;v++){
		int x=0;
		for(int i=1;i<=n;i++) if(a[i]!=0&&a[i]<v) x++;
		int res=0;
		for(int i=0;i<k-x;i++) if(c>=i) res+=1ll*C(c,i)*pw[v-1][i]%mod*pw[m-v+1][c-i]%mod,res%=mod;
		ans=(ans+res)%mod;
	}
	cout<<1ll*ans*ksm(pw[m][c],mod-2)%mod;
}

ARC139D Priority Queue 2

题解
首先把总和拆开，将 ∑i=1nai\sum\limits_{i=1}^n a_i 转化为 ∑j=1m∑i=1n[ai≥j]\sum\limits_{j=1}^m \sum\limits_{i=1}^n [a_i \ge j]。
于是考虑枚举 jj，计算 ∑i=1n[ai≥j]\sum\limits_{i=1}^n [a_i \ge j] 的总和。
设初始时满足 ai≥ja_i \ge j 的 ii 的个数等于 cc，操作过程中一共加了 pp 个大于等于 jj 的数：
  • 若 c≥n−x+1c \ge n-x+1，则最终满足 ai≥ja_i \ge j 的 ii 的个数等于 f(c,p)=max⁡(n−x+1,c+p−k)f(c,p)=\max(n-x+1,c+p-k)；
  • 若 c<n−x+1c \lt n-x+1，则最终满足 ai≥ja_i \ge j 的 ii 的个数等于 f(c,p)=min⁡(n−x+1,c+p)f(c,p)=\min(n-x+1,c+p)。
于是可以得到：
∑i=1n[ai≥j]=∑p=0kf(c,p)(m−j+1)p(j−1)k−p(kp)\sum_{i=1}^n[a_i\ge j]=\sum_{p=0}^k f(c,p)(m-j+1)^p(j-1)^{k-p}{k \choose p}
预处理后直接计算即可。时间复杂度 O(n+mk)\mathcal O(n+mk)。
代码C
#define int long long
const int N=2005,mod=998244353;
int n,m,k,x,a[N],pw[N][N],fac[N],infac[N],ans;
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1,a=a*a%mod;
	}
	return res;
}
int f(int c,int p){
	if(c>=n-x+1) return max(n-x+1,c+p-k);
	else return min(n-x+1,c+p);
}
int C(int n,int m){
	return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void solve(){
	cin>>n>>m>>k>>x;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<=m;i++){
		pw[i][0]=1;
		for(int j=1;j<=k;j++) pw[i][j]=pw[i][j-1]*i%mod;
	}
	fac[0]=infac[0]=1;
	for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;
	infac[k]=ksm(fac[k],mod-2);
	for(int i=k-1;i>0;i--) infac[i]=infac[i+1]*(i+1)%mod;
	for(int j=1;j<=m;j++){
		int c=0;
		for(int i=1;i<=n;i++) if(a[i]>=j) c++;
		for(int p=0;p<=k;p++) ans+=f(c,p)*pw[m-j+1][p]%mod*pw[j-1][k-p]%mod*C(k,p),ans%=mod;
	}
	cout<<ans<<endl;
}

ARC150D Removing Gacha

题解
显然总期望操作次数等于每个点期望操作次数之和，于是考虑对于每个点 uu，计算点 uu 被操作次数的期望。
设点 uu 的深度为 dud_u，那么点 uu 是否还需要被操作只和点 uu 到根路径上的 dud_u 个点的状态有关，所以我们可以只考虑这 dud_u 个点。
于是现在问题转化为了，有 dud_u 个点，每次随机选择一个点，直到每个点都被选择过为止，求第 dud_u 个点被选择次数的期望。
设当前已经选择了 kk 个点，那么有 du−kdu\frac {d_u-k}{d_u} 的概率选择到一个新点，也就是期望 dudu−k\frac {d_u}{d_u-k} 次选择到一个新点。相加可以得到总的期望选择次数等于 ∑k=0du−1dudu−k=du∑k=1du1k\sum\limits_{k=0}^{d_u-1}\frac {d_u}{d_u-k}=d_u\sum\limits_{k=1}^{d_u}\frac {1}{k}，而每个点被选择到的概率相等，所以第 dud_u 个点期望被选择 ∑k=1du1k\sum\limits_{k=1}^{d_u}\frac {1}{k} 次。
将所有点期望操作次数相加，得到答案为 ∑u=1n∑k=1du1k\sum\limits_{u=1}^n \sum\limits_{k=1}^{d_u}\frac {1}{k}。直接计算即可，时间复杂度 O(n)\mathcal O(n)。
代码C
const int N=2e5+5,mod=998244353;
int n,p[N],d[N],ans,fac[N],infac[N],inv[N],pre[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=2;i<=n;i++) cin>>p[i];
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++) inv[i]=1ll*fac[i-1]*infac[i]%mod;
	for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+inv[i])%mod;
	for(int i=1;i<=n;i++) d[i]=d[p[i]]+1,ans=(ans+pre[d[i]])%mod;
	cout<<ans<<endl;
}

ARC165E Random Isolation

题解
由于每个点最多只会被删除一次，且每个连通块不会增大，所以可以将题意转化为：随机一个排列 pp，从 11 到 nn 依次考虑每个点 pip_i，如果点 pip_i 所处的连通块大小大于 kk 则删除点 pip_i，否则不进行操作，求期望删除次数。
设 P(G)P(G) 表示原树的子图 GG 作为一个完整的连通块的出现概率。如果图 GG 包含大于 kk 个点，那么当图 GG 作为一个完整的连通块出现时，一定会进行恰好一次删除操作。所以，期望删除次数就等于每个包含大于 kk 个点的子图 GG 作为一个完整的连通块的出现概率之和，即 ∑∣G∣>kP(G)\sum\limits_{|G|>k} P(G)。
接下来考虑怎么计算 P(G)P(G)。设图 GG 包含 aa 个点，原树中有 bb 个点与图 GG 中的点相连，那么要求只有这 bb 个点在排列中的顺序均在这 aa 个点前，所以 P(G)P(G) 等于 a!b!(a+b)!\dfrac{a!b!}{(a+b)!}。
于是可以进行树形 dp：设 fu,i,jf_{u,i,j} 表示，满足图 GG 中深度最小的点为 uu，包含 ii 个点，以 uu 为根的子树中有 jj 个点与图 GG 中的点相连的原树的子图 GG 的数量。直接从儿子处转移即可。
时间复杂度 O(n4)\mathcal O(n^4)。
代码C
const int N=105,mod=998244353;
int n,k,siz[N],fac[N],infac[N],f[N][N][N],g[N][N],ans;
vector <int> ve[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1;
		a=1ll*a*a%mod;
	}
	return res;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
void dfs(int u,int fa){
	f[u][1][0]=1,siz[u]=1;
	for(auto v:ve[u]){
		if(v==fa) continue;
		dfs(v,u);
		memset(g,0,sizeof g);
		for(int i=0;i<=siz[u];i++) for(int j=0;i+j<=siz[u];j++) for(int p=0;p<=siz[v];p++) for(int q=0;p+q<=siz[v];q++) add(g[i+p][j+q],1ll*f[u][i][j]*f[v][p][q]%mod);	
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[u];j++) f[u][i][j]=g[i][j];
	}
	f[u][0][1]=1;
}
void solve(){
	cin>>n>>k;
	for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u].pb(v),ve[v].pb(u);
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
	dfs(1,0);
	for(int u=1;u<=n;u++){
		for(int i=k+1;i<=siz[u];i++){
			for(int j=0;i+j<=siz[u];j++){
				int p=j+(u!=1);
				add(ans,1ll*f[u][i][j]*fac[i]%mod*fac[p]%mod*infac[i+p]%mod);
			}
		}
	}
	cout<<ans<<endl;
}

P8321 『JROI-4』沈阳大街 2

题解
考虑把 aia_i 看作 11 类数，bib_i 看作 22 类数，将所有 aia_i 和所有 bib_i 扔进一个长度为 2n2n 的数列 cc 中并从大到小排序，每次选出一个 11 类数和 22 类数进行匹配，贡献乘上较小的数的值，将问题转化为求所有匹配方案的贡献之和。
设 fi,jf_{i,j} 表示考虑到数列 cc 的第 ii 项，此时一共匹配了 jj 对数的方案的贡献的和。转移时，首先根据 i,ji,j 和前缀和数组，计算出未匹配的 11 类数数量 xx 和未匹配的 22 类数数量 yy，再根据 ci+1c_{i+1} 的类型分别处理：
  • 若 ci+1c_{i+1} 为 11 类数：
    • 若 y>0y>0：对 ci+1c_{i+1} 进行匹配，fi+1,j+1←fi+1,j+1+y×ci+1×fi,jf_{i+1,j+1} \leftarrow f_{i+1,j+1}+y\times c_{i+1} \times f_{i,j}；
    • 不对 ci+1c_{i+1} 进行匹配，fi+1,j←fi+1,j+fi,jf_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。
  • 若 ci+1c_{i+1} 为 22 类数：
    • 若 x>0x>0：对 ci+1c_{i+1} 进行匹配，fi+1,j+1←fi+1,j+1+x×ci+1×fi,jf_{i+1,j+1} \leftarrow f_{i+1,j+1}+x\times c_{i+1} \times f_{i,j}；
    • 不对 ci+1c_{i+1} 进行匹配，fi+1,j←fi+1,j+fi,jf_{i+1,j} \leftarrow f_{i+1,j}+f_{i,j}。
初始化 f0,0=0f_{0,0}=0，答案即为 f2n,nf_{2n,n}。
时间复杂度 O(n2)\mathcal O(n^2)。
代码C
const int N=5005,mod=998244353;
int n,f[N<<1][N],s[N<<1][3];
pii p[N<<1];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=1;
	for(int i=1;i<=n;i++) cin>>p[n+i].fi,p[n+i].se=2;
	sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
	for(int i=1;i<=n+n;i++) for(int k=1;k<=2;k++) s[i][k]=s[i-1][k]+(p[i].se==k);
	f[0][0]=1;
	for(int i=0;i<n+n;i++){
		for(int j=0;j<=min(s[i][1],s[i][2]);j++){
			int x=s[i][1]-j,y=s[i][2]-j;
			if(p[i+1].se==1){
				if(y>0) add(f[i+1][j+1],1ll*y*p[i+1].fi%mod*f[i][j]%mod);
				add(f[i+1][j],f[i][j]);
			}
			else{
				if(x>0) add(f[i+1][j+1],1ll*x*p[i+1].fi%mod*f[i][j]%mod);
				add(f[i+1][j],f[i][j]);
			}
		}
	}
	int fac=1;
	for(int i=1;i<=n;i++) fac=1ll*fac*i%mod;
	cout<<1ll*ksm(fac,mod-2)*f[n+n][n]%mod<<endl;
}

ARC207A Affinity for Artifacts

题解
设总成本为 ww，第 ii 个灯是第 pip_i 个被点亮的。考虑每个灯节约了多少成本，则显然有：
(∑i=1nai)−w=∑i=1nmin⁡(ai,pi−1)\left(\sum_{i=1}^n a_i\right)-w=\sum_{i=1}^n \min(a_i,p_i-1)
考虑把 aia_i 看作 11 类数，pi−1p_i-1 看作 22 类数，将所有 aia_i 和所有 pi−1p_i-1 扔进一个长度为 2n2n 的数列 cc 中并从大到小排序，每次选出一个 11 类数和 22 类数进行匹配，贡献为较小的数的值。
设 fi,j,kf_{i,j,k} 表示考虑到数列 cc 的第 ii 项，此时一共匹配了 jj 对数，总贡献为 kk 的方案数。转移时，首先根据 i,ji,j 和前缀和数组，计算出未匹配的 11 类数数量 xx 和未匹配的 22 类数数量 yy，再根据 ci+1c_{i+1} 的类型分别处理：
  • 若 ci+1c_{i+1} 为 11 类数：
    • 若 y>0y>0：对 ci+1c_{i+1} 进行匹配，fi+1,j+1,k+ci+1←fi+1,j+1,k+ci+1+y×fi,j,kf_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+y \times f_{i,j,k}；
    • 不对 ci+1c_{i+1} 进行匹配，fi+1,j,k←fi+1,j,k+fi,j,kf_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}。
  • 若 ci+1c_{i+1} 为 22 类数：
    • 若 x>0x>0：对 ci+1c_{i+1} 进行匹配，fi+1,j+1,k+ci+1←fi+1,j+1,k+ci+1+x×fi,j,kf_{i+1,j+1,k+c_{i+1}} \leftarrow f_{i+1,j+1,k+c_{i+1}}+x \times f_{i,j,k}；
    • 不对 ci+1c_{i+1} 进行匹配，fi+1,j,k←fi+1,j,k+fi,j,kf_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k}。
初始化 f0,0,0=1f_{0,0,0}=1。设 v=(∑i=1nai)−xv=\left(\sum\limits_{i=1}^n a_i\right)-x，特判一下 v<0v \lt 0 和 v>n(n−1)2v \gt \frac {n(n-1)}2 的情况，答案即为 ∑i=vn(n−1)2f2n,n,i\sum\limits_{i=v}^{\frac{n(n-1)}{2}} f_{2n,n,i}。
时间复杂度 O(n4)\mathcal O(n^4)。
代码C
const int N=105,mod=998244353;
int n,x,a[N],s[N<<1][3],f[N<<1][N][N*(N-1)/2];
ll sum,v;
pii p[N<<1];
int get(int i,int j){
	int a=s[i][1],b=s[i][2];
	return b-a+j;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	v=sum-x;
	if(v<0) v=0;
	if(v>n*(n-1)/2) v=n*(n-1)/2+1;
	for(int i=1;i<=n;i++) p[i]={a[i],1},p[n+i]={i-1,2};
	sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
	for(int i=1;i<=n+n;i++) for(int j=1;j<=2;j++) s[i][j]=s[i-1][j]+(p[i].se==j);
	f[0][0][0]=1;
	for(int i=0;i<n+n;i++){
		for(int j=0;j<=min(s[i][1],s[i][2]);j++){
			int x=s[i][1]-j,y=s[i][2]-j;
			for(int s=0;s<=n*(n-1)/2;s++){
				if(p[i+1].se==1){
					if(y!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*y%mod);
					add(f[i+1][j][s],f[i][j][s]);
				}
				else{
					if(x!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*x%mod);
					add(f[i+1][j][s],f[i][j][s]);
				}
			}
		}
	}
	int ans=0;
	for(int i=v;i<=n*(n-1)/2;i++) add(ans,f[n+n][n][i]);
	cout<<ans<<endl;
}

ARC121E Directed Tree

题解
将对排列 aa 的计数转化为对其逆排列 bb 的计数，那么此时要求结点 bib_i 不在结点 ii 的子树内。
考虑容斥。设 gig_i 表示钦定 ii 个结点不合法，且只考虑这 ii 个结点的方案数，那么 ans=∑i=0n(−1)i×gi×(n−i)!ans=\sum\limits_{i=0}^n (-1)^i\times g_i\times (n-i)!。
接下来思考如何求 gig_i。设 fu,if_{u,i} 表示以 uu 为根的子树内，钦定了 ii 个结点不合法，且只考虑这 ii 个结点的方案数。考虑转移：
  • 新加入一个儿子时，因为两个子树的不合法的集合是不交的，所以可以直接合并，转移方程为 fu,i+j′←fu,i×fv,jf'_{u,i+j}\leftarrow f_{u,i} \times f_{v,j}；
  • 加入所有儿子后，枚举点 uu 是否合法，得到转移方程为 fu,i+1′←fu,i×(sizu−i−1)+fu,i+1f'_{u,i+1} \leftarrow f_{u,i} \times (siz_u-i-1)+f_{u,i+1}。
于是 gig_i 就等于 f1,if_{1,i}。时间复杂度 O(n2)\mathcal O(n^2)。
代码C
const int N=2005,mod=998244353;
int n,p[N],siz[N],f[N][N],tmp[N],fac[N],ans;
vector <int> ve[N];
void add(int &u,int v){
	u+=v;
	if(u>=mod) u-=mod;
}
void dfs(int u){
	f[u][0]=1;
	for(auto v:ve[u]){
		dfs(v);
		for(int i=0;i<=siz[u];i++) tmp[i]=f[u][i],f[u][i]=0;
		for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[v];j++) add(f[u][i+j],1ll*tmp[i]*f[v][j]%mod);
		siz[u]+=siz[v];
	}
	siz[u]++;
	for(int i=siz[u]-1;i>=0;i--) add(f[u][i+1],1ll*f[u][i]*(siz[u]-i-1)%mod);
}
void solve(){
	cin>>n;
	for(int i=2;i<=n;i++) cin>>p[i],ve[p[i]].pb(i);
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	dfs(1);
	for(int i=0;i<=n;i++){
		if(i&1) add(ans,mod-1ll*f[1][i]*fac[n-i]%mod);
		else add(ans,1ll*f[1][i]*fac[n-i]%mod);
	}
	cout<<ans<<endl;
}

CF2048G Kevin and Matrices

题解
先考虑 min⁡1≤i≤n(max⁡1≤j≤mai,j)<max⁡1≤j≤m(min⁡1≤i≤nai,j)\min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)\lt \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right) 的情况。此时需要满足，存在 xx 使得存在一行都小于 xx，且存在一列都大于等于 xx。显然这两个条件无法同时满足，故这种情况不存在。
接下来考虑 min⁡1≤i≤n(max⁡1≤j≤mai,j)=max⁡1≤j≤m(min⁡1≤i≤nai,j)\min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)= \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right) 的情况。设这个值等于 kk，那么相当于要求：
  • 存在一行的最大值等于 kk，且每一行的最大值都大于等于 kk；
  • 存在一列的最小值等于 kk，且每一列的最小值都小于等于 kk。
设此时的答案为 anskans_k，f(a,b)f(a,b) 表示每一行的最大值都大于等于 aa 且每一列的最小值都小于等于 bb 的方案数，那么做一个二维差分即可得到：
ansk=f(k,k)−f(k+1,k)−f(k,k−1)+f(k+1,k−1)ans_k=f(k,k)-f(k+1,k)-f(k,k-1)+f(k+1,k-1)
于是问题转化为了如何求 f(a,b)f(a,b)。
考虑容斥：
  • 钦定 ii 行的最大值都小于 aa；
  • 对于每一列：
    • 先不考虑列的限制，方案数为 vn−i(a−1)iv^{n-i}(a-1)^i；
    • 再减掉这一列的最小值大于 bb 的方案数，于是需要减去 (v−b)n−i(max⁡(a−b−1,0))i(v-b)^{n-i}(\max(a-b-1,0))^i；
  • 由于每一列是等价的，所以其对答案的贡献为：
(−1)i(ni)(vn−i(a−1)i−(v−b)n−i(max⁡(a−b−1,0))i)m(-1)^i{n\choose i}\left(v^{n-i}(a-1)^i-(v-b)^{n-i}(\max(a-b-1,0))^i\right)^m
这里我们认为 00=10^0=1。预处理组合数后枚举 ii 并快速幂计算即可。
时间复杂度 O(nvlog⁡m)\mathcal O(nv \log m)。
代码C
const int N=1e6+5,mod=998244353;
int n,m,v,fac[N],infac[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1;
		a=1ll*a*a%mod;
	}
	return res;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
void init(int n){
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
}
int C(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int f(int a,int b){
	int res=0;
	for(int i=0;i<=n;i++){
		int val=ad(1ll*ksm(v,n-i)*ksm(a-1,i)%mod,mod-1ll*ksm(v-b,n-i)*ksm(max(a-b-1,0),i)%mod);
		int ans=1ll*C(n,i)*ksm(val,m)%mod;
		if(i&1) add(res,mod-ans);
		else add(res,ans);
	}
	return res;
}
void solve(){
	cin>>n>>m>>v;
	init(n);
	int ans=0;
	for(int k=1;k<=v;k++) add(ans,(0ll+f(k,k)-f(k+1,k)-f(k,k-1)+f(k+1,k-1)+mod+mod)%mod);
	cout<<ans<<endl;
}

P7154 [USACO20DEC] Sleeping Cows P

题解
为了区分「等待被匹配」和「没有被匹配」，在本文中，若一个奶牛 / 牛棚没有被匹配，则称它被扔掉了。
首先分析一下极大匹配的性质：
  • 如果存在一个奶牛 ii 被扔掉了，那么所有满足 si≤tjs_i \le t_j 的牛棚 jj 必须被匹配；
  • 如果存在一个牛棚 jj 被扔掉了，那么所有满足 si≤tjs_i \le t_j 的奶牛 ii 必须被匹配。
于是考虑把所有 sis_i 和 tjt_j 都扔进数组 aa 里，将数组 aa 排序（若 si=tjs_i=t_j 则 sis_i 在前）之后做一个 dp：设 fi,j,0/1f_{i,j,0/1} 表示考虑到 aia_i，在此之前有 jj 个奶牛正在等待被匹配，且之前有 / 没有被扔掉的奶牛；注意这 jj 个奶牛必须在之后被全部匹配。
对于转移方程，考虑分类讨论：
  • 若 ai+1a_{i+1} 为奶牛（即 ai+1a_{i+1} 属于 ss）：
    • fi+1,j+1,0←fi+1,j+1,0+fi,j,0f_{i+1,j+1,0} \leftarrow f_{i+1,j+1,0}+f_{i,j,0}（保留该奶牛）；
    • fi+1,j,0←fi+1,j,0+fi,j,0f_{i+1,j,0} \leftarrow f_{i+1,j,0}+f_{i,j,0}（扔掉该奶牛）；
    • fi+1,j+1,1←fi+1,j+1,1+fi,j,1f_{i+1,j+1,1} \leftarrow f_{i+1,j+1,1}+f_{i,j,1}（保留该奶牛）；
    • fi+1,j,0←fi+1,j,0+fi,j,1f_{i+1,j,0}\leftarrow f_{i+1,j,0}+f_{i,j,1}（扔掉该奶牛）。
  • 若 ai+1a_{i+1} 为牛棚（即 ai+1a_{i+1} 属于 tt）：
    • fi+1,j−1,0←fi+1,j−1,0+j×fi,j,0f_{i+1,j-1,0} \leftarrow f_{i+1,j-1,0}+j\times f_{i,j,0}（选择一个奶牛进行匹配）；
    • fi+1,j−1,1←fi+1,j−1,1+j×fi,j,1f_{i+1,j-1,1} \leftarrow f_{i+1,j-1,1}+j\times f_{i,j,1}（选择一个奶牛进行匹配）；
    • fi+1,j,1←fi+1,j,1+fi,j,1f_{i+1,j,1}\leftarrow f_{i+1,j,1}+f_{i,j,1}（扔掉该牛棚）。
答案即为 f2n,0,0+f2n,0,1f_{2n,0,0}+f_{2n,0,1}。时间复杂度 O(n2)\mathcal O(n^2)。
代码C
const int N=3005,mod=1e9+7;
int n,m,f[N<<1][N][2];
pii p[N<<1];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n,m=n+n;
	for(int i=1;i<=n;i++) cin>>p[i].fi,p[i].se=0;
	for(int i=1;i<=n;i++) cin>>p[i+n].fi,p[i+n].se=1;
	sort(p+1,p+1+m);
	f[0][0][1]=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<=min(n,i);j++){
			if(p[i+1].se==0){
				add(f[i+1][j+1][0],f[i][j][0]);
				add(f[i+1][j][0],f[i][j][0]);
				add(f[i+1][j+1][1],f[i][j][1]);
				add(f[i+1][j][0],f[i][j][1]);
			}
			else{
				add(f[i+1][j-1][0],1ll*j*f[i][j][0]%mod);
				add(f[i+1][j-1][1],1ll*j*f[i][j][1]%mod);
				add(f[i+1][j][1],f[i][j][1]);
			}
		}
	}
	cout<<(f[m][0][0]+f[m][0][1])%mod<<endl;
}

P14364 [CSP-S 2025] 员工招聘

题解
设集合 U={i∣si=1}U=\{i \mid s_i=1\}，考虑钦定一个集合 S⊆US \subseteq U，满足：
  • 对于所有 i∈Si\in S，第 ii 个位置的人会被录取，即要求 ci>∑j=1i−1[j∉S]c_i \gt \sum\limits_{j=1}^{i-1} [j \notin S]；
  • 对于所有 i∈U∖Si\in U\setminus S，第 ii 个位置的人不会被录取，即要求 ci≤∑j=1i−1[j∉S]c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]。
考虑容斥，把第一个条件的形式与第二个条件统一。具体地，钦定一个集合 T⊆ST \subseteq S，满足：
  • 对于所有 i∈Ti \in T，第 ii 个位置的人不会被录取，即要求 ci≤∑j=1i−1[j∉S]c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]；
  • 对于所有 i∈S∖Ti \in S\setminus T，第 ii 个位置的人没有要求。
容斥系数为 (−1)∣T∣(-1)^{|T|}。
考虑从前往后 dp。设 fi,j,kf_{i,j,k} 表示，考虑到第 ii 个位置，此时一共有 jj 个数在 SS 中，kk 个数在 TT 中，且仅考虑 T∪(U∖S)T \cup (U \setminus S) 中的位置填的数的方案数。初始化 f0,0,0=1f_{0,0,0}=1，设 ai=∑j=1n[cj≤i]a_i=\sum\limits_{j=1}^n [c_j \le i]，bi=∑j=1i[sj=1]b_i=\sum\limits_{j=1}^i [s_j=1]，考虑转移：
  • 若 si+1=0s_{i+1}=0，fi+1,j,k←fi,j,kf_{i+1,j,k} \leftarrow f_{i,j,k}；
  • 若 si+1=1s_{i+1}=1：
    • 令 i+1∈U∖Si+1 \in U\setminus S，fi+1,j,k←fi+1,j,k+fi,j,k×(ai−j−k−bi+j)f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)；
    • 令 i+1∈S∖Ti+1 \in S\setminus T，fi+1,j+1,k←fi+1,j+1,k+fi,j,kf_{i+1,j+1,k} \leftarrow f_{i+1,j+1,k}+f_{i,j,k}；
    • 令 i+1∈Ti+1 \in T，fi+1,j+1,k+1←fi+1,j+1,k+1+fi,j,k×(ai−j−k−bi+j)f_{i+1,j+1,k+1} \leftarrow f_{i+1,j+1,k+1}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)。
其中，系数为 ai−j−k−bi+ja_{i-j}-k-b_i+j 的原因是：当前位置填的数需要小于等于 i−ji-j，且之前已经用了 k+bi−jk+b_i-j 个这样的数。
答案即为 ∑j=mn∑k=0jfn,j,k×(−1)k×(n−bn+j−k)!\sum\limits_{j=m}^n \sum\limits_{k=0}^j f_{n,j,k} \times (-1)^k \times (n-b_n+j-k)!，其中 n−bn+j−kn-b_n+j-k 是满足 i∉T∪(U∖S)i \notin T \cup (U \setminus S) 的 ii 的数量，这些位置上的数可以任意排列。
使用滚动数组优化，空间复杂度 O(n2)\mathcal O(n^2)，时间复杂度 O(n3)\mathcal O(n^3)。
代码C
const int N=505,mod=998244353;
int n,m,c[N],s[N],a[N],b[N],f[2][N][N],fac[N],ans;
string str;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n>>m>>str;
	for(int i=1;i<=n;i++) cin>>c[i],a[c[i]]++;
	for(int i=1;i<=n;i++) s[i]=(str[i-1]=='1'),b[i]=b[i-1]+s[i];
	for(int i=0;i<=n;i++) a[i]+=a[i-1];
	f[0][0][0]=1,fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<n;i++){
		int t=i&1;
		memset(f[t^1],0,sizeof f[t^1]);
		for(int j=0;j<=b[i];j++){
			for(int k=0;k<=j;k++){
				if(s[i+1]==0) add(f[t^1][j][k],f[t][j][k]);
				else{
					add(f[t^1][j+1][k],f[t][j][k]);
					int x=a[i-j]-k-b[i]+j;
					add(f[t^1][j][k],1ll*f[t][j][k]*x%mod);
					add(f[t^1][j+1][k+1],1ll*f[t][j][k]*x%mod);
				}
			}
		}
	}
	for(int j=m;j<=b[n];j++){
		for(int k=0;k<=j;k++){
			int x=n-b[n]+j-k;
			if(k&1) add(ans,mod-1ll*f[n&1][j][k]*fac[x]%mod);
			else add(ans,1ll*f[n&1][j][k]*fac[x]%mod);
		}
	}
	cout<<ans<<endl;
}

CF2129D Permutation Blackhole

题解
由于对白色区间内的某个点染色后，这个区间会分成两个互不干扰的白色子区间，因此考虑区间 dp：设 fl,r,x,yf_{l,r,x,y} 表示，位置 l−1l-1 和位置 r+1r+1 已经被染色，只考虑区间 [l,r][l,r] 内的贡献和被染色的相对顺序，位置 l−1l-1 的得分增加了 xx 且位置 r+1r+1 的得分增加了 yy 的方案数。
由于对同一个数造成多次贡献会导致区间长度每次减半，所以一个数的得分上限是 O(log⁡n)\mathcal O(\log n) 级别的。于是我们可以知道，只有数组 ff 的前两维是 O(n)\mathcal O(n) 的，而后两维都是 O(log⁡n)\mathcal O(\log n) 的。
设 wl,r,kw_{l,r,k} 表示对白色区间 [l,r][l,r] 中的位置 kk 染色所造成贡献的位置，那么有：
  • 若 r=nr=n，则 wl,r,k=l−1w_{l,r,k}=l-1；
  • 否则，若 l=1l=1，则 wl,r,k=r+1w_{l,r,k}=r+1；
  • 否则，若 2k≤l+r2k\le l+r，则 wl,r,k=l−1w_{l,r,k}=l-1。
  • 否则，wl,r,k=r+1w_{l,r,k}=r+1。
转移考虑枚举区间 [l,r][l,r] 内第一个被染色的位置 kk，分类讨论：
  • 若 sk=−1s_k=-1，则 fl,r,x,y←fl,r,x,y+fl,k−1,x−[wl,r,k=l−1],y′×fk+1,r,x′,y−[wl,r,k=r+1]×(r−lk−l)f_{l,r,x,y}\leftarrow f_{l,r,x,y}+f_{l,k-1,x-[w_{l,r,k}=l-1],y'} \times f_{k+1,r,x',y-[w_{l,r,k}=r+1]} \times {r-l \choose k-l}；
  • 若 sk≠−1s_k\ne-1，则 fl,r,x,y←fl,r,x,y+fl,k−1,x−[wl,r,k=l−1],v×fk+1,r,sk−v,y−[wl,r,k=r+1]×(r−lk−l)f_{l,r,x,y}\leftarrow f_{l,r,x,y}+f_{l,k-1,x-[w_{l,r,k}=l-1],v} \times f_{k+1,r,s_k-v,y-[w_{l,r,k}=r+1]} \times {r-l \choose k-l}。
其中，sk≠−1s_k\ne-1 的情况可以直接枚举 vv，而 sk=−1s_k=-1 的情况可以先计算 ∑y′fl,k−1,x−[wl,r,k=l−1],y′\sum_{y'} f_{l,k-1,x-[w_{l,r,k}=l-1],y'} 和 ∑x′fk+1,r,x′,y−[wl,r,k=r+1]\sum_{x'} f_{k+1,r,x',y-[w_{l,r,k}=r+1]} 再相乘，做到每次转移 O(nlog⁡n)\mathcal O(n \log n)。
对于所有满足 si≤0s_i\le 0 的 ii，初始化 fi,i,[wi,i,i=i−1],[wi,i,i=i+1]←1f_{i,i,[w_{i,i,i}=i-1],[w_{i,i,i}=i+1]}\leftarrow 1，并对于所有不大于 nn 的非负整数 ii，初始化 fi+1,i,0,0←1f_{i+1,i,0,0}\leftarrow 1，那么答案即为 f1,n,1,0f_{1,n,1,0}。
时间复杂度 O(n3log⁡3n)\mathcal O(n^3 \log^3 n)。
代码C
const int N=105,L=8,mod=998244353;
int n,s[N],fac[N],infac[N],f[N][N][L][L];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
int choose(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int w(int l,int r,int k){
	if(r==n) return l-1;
	else if(l==1) return r+1;
	else if(k+k<=l+r) return l-1;
	else return r+1;
}
void solve(){
	cin>>n;
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
	for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) for(int x=0;x<L;x++) for(int y=0;y<L;y++) f[i][j][x][y]=0;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) if(s[i]>L+L-2) return cout<<0<<endl,void();
	for(int i=1;i<=n;i++) if(s[i]<=0) f[i][i][w(i,i,i)==i-1][w(i,i,i)==i+1]=1;
	for(int i=0;i<=n;i++) f[i+1][i][0][0]=1;
	for(int len=2;len<=n;len++){
		for(int l=1,r=len;r<=n;l++,r++){
			for(int x=0;x<L;x++){
				for(int y=0;y<L;y++){
					for(int k=l;k<=r;k++){
						if(s[k]==-1){
							int sum1=0,sum2=0;
							for(int b=0;b<L;b++) add(sum1,f[l][k-1][x-(w(l,r,k)==l-1)][b]);
							for(int a=0;a<L;a++) add(sum2,f[k+1][r][a][y-(w(l,r,k)==r+1)]);
							add(f[l][r][x][y],1ll*sum1*sum2%mod*choose(r-l,k-l)%mod);
						}
						else{
							for(int v=0;v<L;v++){
								if(s[k]-v>=L||s[k]-v<0) continue;
								int val1=f[l][k-1][x-(w(l,r,k)==l-1)][v],val2=f[k+1][r][s[k]-v][y-(w(l,r,k)==r+1)];
								add(f[l][r][x][y],1ll*val1*val2%mod*choose(r-l,k-l)%mod);
							}
						}
					}
				}
			}
		}
	}
	cout<<f[1][n][1][0]<<endl;
}

P11363 [NOIP2024] 树的遍历

题解
对于原树中的某个原点 uu 和所有与其相邻的原边 (u,v1),…,(u,vd)(u,v_1),\dots,(u,v_d)，显然在新树中 (u,v1),…,(u,vd)(u,v_1),\dots,(u,v_d) 之间的新边会形成一条链。
接下来分析新树的构建过程。不妨设遍历起始边为 (x,y)(x,y)：
  • 把树从 (x,y)(x,y) 处分成两部分，并让两部分分别以 xx 和 yy 为根；
  • 对于每部分中的每个结点 uu，设其父亲为 fuf_u，则所有与 uu 相邻的原边之间的新边形成的链一定满足 (u,fu)(u,f_u) 为链的一个端点，而其他原边的顺序无所谓；其中 fx=yf_x=y，fy=xf_y=x。
有一个巧妙的想法是，当新树固定时，对于每个结点 uu，设所有所有与 uu 相邻的原边之间的新边形成的链的另一个端点为 (u,su)(u,s_u)，把 sus_u 看成 uu 的重儿子，则这棵树的两部分相当于各进行了一次树链剖分！设以 xx 为链顶的重链的链底为 aa，以 yy 为链顶的重链的链底为 bb，则根据树链剖分的性质可以得到，把两部分拼起来之后，原树中一定只有恰好一条从叶子到叶子的重链 path(a,b)\boldsymbol{\bold{path}(a,b)}。
然后我们反过来考虑，当 path(a,b)\text{path}(a,b) 固定时，有多少种新树满足条件。显然，对于 path(a,b)\text{path}(a,b) 上的点 uu（不包括 aa 和 bb），所有与 uu 相邻的原边之间的新边形成的链的两个端点已经固定，方案数为 (degu−2)!(deg_u-2)!；而对于不在 path(a,b)\text{path}(a,b) 上的点 uu，所有与 uu 相邻的原边之间的新边形成的链的一个端点是固定的，方案数为 (degu−1)!(deg_u-1)!；拼起来就能得到，当 path(a,b)\text{path}(a,b) 固定时，满足条件的新树的数量为：
∏u∈path(a,b)(degu−2)!∏u∉path(a,b)(degu−1)!\prod_{u\in\text{path}(a,b)} (deg_u-2)! \prod_{u \notin\text{path}(a,b)} (deg_u-1)!
变形一下可得：
∏u=1n(degu−1)!∏u∈path(a,b)(degu−1)−1\prod_{u=1}^n (deg_u-1)! \prod_{u \in\text{path}(a,b)} (deg_u-1)^{-1}
这里认为 0−1=10^{-1}=1。
注意需要满足 path(a,b)\text{path}(a,b) 上要有至少一条给定的关键边，因为我们要在 path(a,b)\text{path}(a,b) 上选择一条边来构建新树。
于是我们可以任选一个 degdeg 不小于 22 的点为树的根进行 dp：设 dpu,0/1dp_{u,0/1} 表示在以结点 uu 为根的子树内，从叶子 ll 到结点 uu 的路径上没有 / 有关键边的所有叶子 ll 的 ∏v∈path(l,u)(degv−1)−1\prod\limits_{v \in \text{path}(l,u)}(deg_v-1)^{-1} 之和。转移时枚举儿子并计算其对 dp 值和答案的贡献即可。
时间复杂度 O(n)\mathcal O(n)。
代码CPP
const int N=1e5+5,mod=1e9+7;
vector <pii> ve[N];
int n,k,r,e[N];
ll dp[N][2],fac[N],infac[N],inv[N],ans,pro;
bool vis[N];
int ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void dfs(int u,int f){
	for(auto p:ve[u]){
		int v=p.fi;
		if(v==f) continue;
		dfs(v,u);
		if(vis[p.se]){
			(ans+=dp[v][0]*dp[u][0]+dp[v][0]*dp[u][1]+dp[v][1]*dp[u][0]+dp[v][1]*dp[u][1])%=mod;
			(dp[u][1]+=dp[v][0]*inv[ve[u].size()-1]+dp[v][1]*inv[ve[u].size()-1])%=mod;
		}
		else{
			(ans+=dp[v][0]*dp[u][1]+dp[v][1]*dp[u][0]+dp[v][1]*dp[u][1])%=mod;
			(dp[u][1]+=dp[v][1]*inv[ve[u].size()-1])%=mod;
			(dp[u][0]+=dp[v][0]*inv[ve[u].size()-1])%=mod;
		}
	}
//	cout<<inv[ve[u].size()-1]<<' '<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<endl;
	if(ve[u].size()==1) dp[u][0]=1;
}
void solve(){
	cin>>n>>k;
	fac[0]=1,infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=1;i--) infac[i]=infac[i+1]*(i+1)%mod;
	for(int i=n-1;i>=1;i--) inv[i]=fac[i-1]*infac[i]%mod;
	for(int i=1;i<=n;i++) ve[i].clear(),vis[i]=0,dp[i][0]=dp[i][1]=0;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		ve[u].pb({v,i});
		ve[v].pb({u,i});
	}
	for(int i=1;i<=k;i++) cin>>e[i],vis[e[i]]=1;
	if(n==2) return cout<<1<<endl,void();
	for(int i=1;i<=n;i++) if(ve[i].size()>=2) r=i;
	pro=1,ans=0;
	dfs(r,0);
	for(int i=1;i<=n;i++) pro=pro*fac[ve[i].size()-1]%mod;
	cout<<ans*pro%mod<<endl;
}

ARC118E Avoid Permutations

题解
直接做有点困难，因此考虑钦定一些尚未确定的障碍点在路径上。设被钦定的障碍点的集合为 TT 时，满足条件的路径数为 c(T)c(T)，则根据容斥原理可知答案可以表示为 ∑T(−1)∣T∣c(T)\sum_{T} (-1)^{|T|} c(T)。
设 fi,j,k,0/1,0/1f_{i,j,k,0/1,0/1} 表示，考虑到第 ii 行第 jj 列的格子，此时一共钦定了 kk 个障碍点，第 ii 行没有 / 有障碍点，第 jj 列没有 / 有障碍点时的方案数。初始时 f0,0,0,1,1=1f_{0,0,0,1,1}=1。
设 xi=0/1x_i=0/1 表示第 ii 行没有 / 有确定的障碍点，yj=0/1y_j=0/1 表示第 jj 列没有 / 有确定的障碍点。对于 fi,j,k,a,bf_{i,j,k,a,b}，考虑转移：
  • 如果 (i,j)(i,j) 处有障碍点，则不做转移；
  • 如果 (i,j)(i,j) 处没有障碍点：
    • 如果 i≤ni \le n：
      • 不在 (i,j)(i,j) 处钦定障碍点，fi+1,j,k,xi+1,b←fi+1,j,k,xi+1,b+fi,j,k,a,bf_{i+1,j,k,x_{i+1},b} \leftarrow f_{i+1,j,k,x_{i+1},b}+f_{i,j,k,a,b}。
      • 如果 a=0a=0 且 b=0b=0：在 (i,j)(i,j) 处钦定障碍点，fi+1,j,k+1,xi+1,1←fi+1,j,k+1,xi+1,1+fi,j,k,a,bf_{i+1,j,k+1,x_{i+1},1} \leftarrow f_{i+1,j,k+1,x_{i+1},1}+f_{i,j,k,a,b}。
    • 如果 j≤nj \le n：
      • 不在 (i,j)(i,j) 处钦定障碍点，fi,j+1,k,a,yj+1←fi,j+1,k,a,yj+1+fi,j,k,a,bf_{i,j+1,k,a,y_{j+1}} \leftarrow f_{i,j+1,k,a,y_{j+1}}+f_{i,j,k,a,b}。
      • 如果 a=0a=0 且 b=0b=0：在 (i,j)(i,j) 处钦定障碍点，fi,j+1,k+1,1,yj+1←fi,j+1,k+1,1,yj+1+fi,j,k,a,bf_{i,j+1,k+1,1,y_{j+1}} \leftarrow f_{i,j+1,k+1,1,y_{j+1}}+f_{i,j,k,a,b}。
设 mm 表示初始时 −1-1 的数量，答案即为：
∑k=0m(−1)k×fn+1,n+1,k,0,0×(m−k)!\sum_{k=0}^m (-1)^k \times f_{n+1,n+1,k,0,0} \times (m-k)!
其中乘 (m−k)!(m-k)! 是因为没有被钦定的 pp 可以在剩余的 (m−k)(m-k) 个位置任意排列。
时间复杂度 O(n3)\mathcal O(n^3)。
代码C
const int N=205,mod=998244353;
int n,m,a[N],fac[N],f[N][N][N][2][2],ans;
bool vis[N][N],x[N],y[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n,fac[0]=1,f[0][0][0][1][1]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=-1) vis[i][a[i]]=1,x[i]=1,y[a[i]]=1;
		else m++;
	}
	for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=n+1;j++){
			if(vis[i][j]) continue;
			for(int k=0;k<=min(i,j);k++){
				for(int a=0;a<=1;a++){
					for(int b=0;b<=1;b++){
						if(i<=n){
							add(f[i+1][j][k][x[i+1]][b],f[i][j][k][a][b]);
							if(!a&&!b) add(f[i+1][j][k+1][x[i+1]][1],f[i][j][k][a][b]);
						}
						if(j<=n){
							add(f[i][j+1][k][a][y[j+1]],f[i][j][k][a][b]);
							if(!a&&!b) add(f[i][j+1][k+1][1][y[j+1]],f[i][j][k][a][b]);
						}
					}
				}
			}
		}
	}
	for(int k=0;k<=m;k++){
		if(k&1) add(ans,mod-1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
		else add(ans,1ll*f[n+1][n+1][k][0][0]*fac[m-k]%mod);
	}
	cout<<ans<<endl;
}

ARC124E Pass to Next

题解
设第 ii 个人给下一个人传了 cic_i 个球，第 ii 个人的手中最终有 xix_i 个球，则有 xi=ai−ci+ci−1x_i=a_i-c_i+c_{i-1}，其中我们认为 c0=cnc_0=c_n。显然，若 min⁡i=1nci>0\min\limits_{i=1}^n c_i \gt 0 则可以通过使所有 cic_i 都减去 11 的方式保持最终局面不变，而所有 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 所形成的最终局面又两两不同，也就是说所有 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的操作序列 cc 与最终局面 xx 形成了双射。因此，我们考虑转化计数对象：对于所有 ci∈[0,ai]c_i \in [0,a_i] 且 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的数列 cc，计算 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 的和。
先上一个经典手法，把所有 ci∈[0,ai]c_i \in [0,a_i] 且 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和转化为，所有 ci∈[0,ai]c_i \in [0,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和减去所有 ci∈[1,ai]c_i \in [1,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。
接下来尝试计算所有 ci∈[0,ai]c_i \in [0,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。考虑其组合意义：对于所有最终局面，从每个人手中选一个球的方案数。
设 fif_i 表示考虑完前 i−1i-1 个人且第 ii 个人选择了自己的球的方案数，gig_i 表示考虑完前 ii 个人且第 ii 个人选择了上一个人传来的球的方案数。这样设计状态是因为，若第 ii 个人选择了自己的球，则其贡献需要在 fif_i 向 fi+1f_{i+1} 或 gi+1g_{i+1} 转移时计算，而若第 ii 个人选择了上一个人传来的球，则其贡献需要在 fi−1f_{i-1} 或 gi−1g_{i-1} 向 gig_i 转移时计算。
转移方程为：
  • fi+1←fi⋅∑v=0aiv+gi⋅∑v=0ai1f_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i} v+g_i \cdot \sum\limits_{v=0}^{a_i} 1（枚举留下几个球）；
  • gi+1←fi⋅∑v=0aiv(ai−v)+gi⋅∑v=0aivg_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i} v(a_i-v)+g_i \cdot \sum\limits_{v=0}^{a_i} v（枚举传了几个球）。
由于这是一个环，所以我们还需要枚举一下第 11 个人的状态：先初始化 f1=1,g1=0f_1=1,g_1=0，dp 一轮，给答案加上 fn+1f_{n+1}；再初始化 f1=0,g1=1f_1=0,g_1=1，重新 dp 一轮，给答案加上 gn+1g_{n+1}。
解决了 ci∈[0,ai]c_i \in [0,a_i] 的情况，ci∈[1,ai]c_i \in [1,a_i] 的情况是基本相同的，但由于要求每个人都要传递至少一个球，所以转移方程变为了：
  • fi+1←fi⋅∑v=0ai−1v+gi⋅∑v=0ai−11f_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i-1} v+g_i \cdot \sum\limits_{v=0}^{a_i-1} 1（枚举留下几个球）；
  • gi+1←fi⋅∑v=1aiv(ai−v)+gi⋅∑v=1aivg_{i+1} \leftarrow f_i \cdot \sum\limits_{v=1}^{a_i} v(a_i-v)+g_i \cdot \sum\limits_{v=1}^{a_i} v（枚举传了几个球）。
其余部分都是一样的，按照上面的方法计算即可。
时间复杂度 O(n)\mathcal O(n)。
代码C
const int N=3e5+5,mod=998244353,inv2=499122177,inv6=166374059;
int n,a[N],f[N],g[N];
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int s1(int x){
	return 1ll*x*(x+1)%mod*inv2%mod;
}
int s2(int x){
	return 1ll*x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}
int work(int x,int y){
	if(!x) f[1]=1,g[1]=0;
	else f[1]=0,g[1]=1;
	for(int i=1;i<=n;i++){
		f[i+1]=ad(1ll*f[i]*s1(a[i]-y)%mod,1ll*g[i]*(a[i]-y+1)%mod);
		g[i+1]=ad(1ll*f[i]*ad(1ll*a[i]*s1(a[i])%mod,mod-s2(a[i]))%mod,1ll*g[i]*s1(a[i])%mod);
	}
	if(!x) return f[n+1];
	else return g[n+1];
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<ad(ad(work(0,0),work(1,0)),mod-ad(work(0,1),work(1,1)))<<endl;
}

ARC184D Erase Balls 2D

题解
将所有球按照 XiX_i 排序，那么第 ii 个球满足 Xi=iX_i=i。显然选择的球的顺序并不重要，我们只需要明确哪些球被选了。为了方便，我们在 (0,n+1)(0,n+1) 和 (n+1,0)(n+1,0) 处各添加一个球，并强制选择这两个球。
设选择的球所组成的集合为 S={a1,a2,…,am} (0=a1<a2<⋯<am=n+1)S=\{a_1,a_2,\dots,a_m\}\ (0=a_1 \lt a_2 \lt \dots \lt a_m=n+1)，那么显然有 Ya1>Ya2>⋯>YamY_{a_1}\gt Y_{a_2}\gt \dots \gt Y_{a_m}。
设剩余的球所组成的集合为 f(S)f(S)：
  • 对于 u∈f(S)u \in f(S) 且 x∉f(S)x \not\in f(S)，设 aj<u<aj+1a_j \lt u \lt a_{j+1}，则显然有 Yaj>Yu>Yaj+1Y_{a_j}\gt Y_u \gt Y_{a_{j+1}}；
  • 对于 v∉f(S)v \not\in f(S)，设 aj<v<aj+1a_j \lt v \lt a_{j+1}，则显然有 Yaj<YvY_{a_j} \lt Y_v 或 Yv<Yaj+1Y_v \lt Y_{a_{j+1}}。
直接对本质不同的 f(S)f(S) 进行计数比较困难，因此可以转化计数对象，对选择的球所组成的集合 SS 进行计数。
显然不漏容易做到，于是问题变成了如何做到不重。考虑把 f(S)f(S) 的贡献转化到满足下列条件的集合 TT 上：
  • f(T)=f(S)f(T)=f(S)；
  • 对于任意 u∉Tu \not\in T，f({u}∪T)≠f(S)f\big(\{u\} \cup T\big) \ne f(S)；换句话说，即再选择任意一个球都会导致 f(T)f(T) 变化。
显然满足条件的集合 TT 是唯一的，因为了第二个条件相当于要求了集合 TT 是极大的。
于是现在只需要统计有多少个集合 TT 满足上面的条件即可。设 fif_i 表示考虑完前 ii 个球且选择了第 ii 个球的满足条件的集合 TT 的数量。转移时枚举 0≤j<i0 \le j \lt i 且 Yj>YiY_j \gt Y_i 的整数 jj，表示上一个选择的球为 jj，判断是否能从 jj 转移到 ii：
  • 若存在 j<k<ij \lt k \lt i，使得对于任意 j<u<kj \lt u \lt k 都不满足 Yi<Yu<YkY_i \lt Y_u \lt Y_k 且对于任意 k<v<ik \lt v \lt i 都不满足 Yk<Yv<YjY_k \lt Y_v \lt Y_j（即选择 kk 不会导致 f(T)f(T) 变化），则不能从 jj 转移到 ii，否则可以从 jj 转移到 ii。
于是做一个二维前缀和即可 O(n)\mathcal O(n) 检验是否能从 jj 转移到 ii。总时间复杂度 O(n3)\mathcal O(n^3)。
代码C
const int N=305,mod=998244353;
int n,v[N],s[N][N],f[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
bool check(int ax,int ay,int bx,int by){
	return s[ax][ay]-s[ax][by-1]-s[bx-1][ay]+s[bx-1][by-1]==1;
}
void solve(){
	cin>>n,s[1][n+2]++,s[n+2][1]++,v[1]=n+2,v[n+2]=1;
	for(int i=1,x,y;i<=n;i++) cin>>x>>y,x++,y++,v[x]=y,s[x][y]++;
	for(int x=1;x<=n+2;x++) for(int y=1;y<=n+2;y++) s[x][y]=s[x][y]+s[x-1][y]+s[x][y-1]-s[x-1][y-1];
	f[1]=1;
	for(int i=2;i<=n+2;i++){
		for(int j=i-1;j>=1;j--){
			if(v[j]<v[i]) continue; 
			bool flag=1;
			for(int k=j+1;k<i;k++){
				if(check(k,v[k],j,v[i])&&check(i,v[j],k,v[k])){
					flag=0;
					break;
				}
			}
			if(flag) add(f[i],f[j]);
		}
	}
	cout<<f[n+2]<<endl;
}

AGC020E Encoding Subsets

题解
首先考虑对于一个确定的长度为 nn 的 01\texttt{01} 串 SS，如何求 SS 的编码方式数。
设 fl,rf_{l,r} 表示 Sl∼SrS_l\sim S_r 的编码方式数，gl,rg_{l,r} 表示 Sl∼SrS_l\sim S_r 缩成一个括号或单个字符的编码方式数。
对于 fl,rf_{l,r}，枚举 Sl∼SrS_l\sim S_r 编码后第一个字符的来源，得到转移方程：
fl,r=∑m=lrgl,m×fm+1,rf_{l,r}=\sum_{m=l}^{r} g_{l,m} \times f_{m+1,r}
对于 gl,rg_{l,r}，枚举 Sl∼SrS_l\sim S_r 的循环节 dd，得到转移方程：
gl,r=∑d∣len,d≠lenw(d,l,r)×fl,l+d−1g_{l,r}=\sum_{d\mid len,d \ne len} w(d,l,r) \times f_{l,l+d-1}
其中，len=r−l+1len=r-l+1，若 dd 为 Sl∼SrS_l\sim S_r 的循环节则 w(d,l,r)=1w(d,l,r)=1，否则 w(d,l,r)=0w(d,l,r)=0。
直接计算即可得到 SS 的编码方式数 f1,nf_{1,n}。
接下来考虑如何计算长度为 nn 的 01\texttt{01} 串 SS 的所有子集的编码方式数之和。
同理，设 fSf_S 表示 SS 的所有子集的编码方式数之和，gSg_S 表示 SS 的所有子集的缩成一个括号或单个字符的编码方式数之和。
对于 fSf_S，仍然枚举 SS 编码后第一个字符的来源，得到转移方程：
fS=∑m=1ngS[1,m]×fS[m+1,n]f_S=\sum_{m=1}^{n} g_{S[1,m]} \times f_{S[m+1,n]}
对于 gSg_S，同样枚举 SS 的循环节 dd，得到转移方程：
gS=∑d∣n,d≠nfc(S,d)g_S=\sum_{d \mid n,d \ne n} f_{c(S,d)}
其中 c(S,d)c(S,d) 表示，把 SS 分成长度为 dd 的 nd\dfrac{n}{d} 个 01\texttt{01} 串，每个 01\texttt{01} 串按位与的结果。
记忆化搜索即可。有效状态数并不多，足以通过。
代码C
const int mod=998244353;
string s;
map <string,int> f,g;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int G(string s);
int F(string s){
	if(s=="") return 1;
	if(f.count(s)) return f[s];
	int n=s.size(),ans=0;
	for(int i=1;i<=n;i++) add(ans,1ll*G(s.substr(0,i))*F(s.substr(i,n-i))%mod);
	return f[s]=ans;
}
int G(string s){
	if(s=="") return 1;
	if(s=="0") return 1;
	if(s=="1") return 2;
	if(g.count(s)) return g[s];
	int n=s.size(),ans=0;
	for(int d=1;d<n;d++){
		if(n%d!=0) continue;
		string t="";
		for(int i=0;i<d;i++){
			bool x=1;
			for(int j=i;j<n;j+=d) x&=(s[j]=='1');
			t+=x+'0';
		}
		add(ans,F(t));
	}
	return g[s]=ans;
}
void solve(){
	cin>>s;
	cout<<F(s)<<endl;
}

P10813 【MX-S2-T4】 换

题解
显然，序列 aa 是否能通过操作排好序只和每个元素的相对大小有关，因此我们可以先求出将其离散化后的序列 bb。对于序列 bb，设其值域为 [1,w][1,w]，我们考虑序列 bb 拆成 w+1w+1 个 0101 串 c0,c1,…,cwc_0,c_1,\dots,c_w，其中 ci,j=[bj≥i]c_{i,j}=[b_j \ge i]，那么序列 bb 能通过操作排好序当且仅当它拆成的 w+1w+1 个 0101 串都能通过操作排好序。
我们可以暴力求出每个 0101 串是否合法，并把每个序列 bb 看成一个 00⋯000\cdots0 到 11⋯111\cdots1 的长度为 ww 的路径，对合法的 0101 串做一个 dp 即可得到合法的序列 bb 的数量。具体地，设 fi,sf_{i,s} 表示，当前是路径上的第 ii 个 0101 串，其状态表示为 ss，此时满足条件的序列 bb 的数量。初始化 f0,0f_{0,0}，转移方程为：
fi,s={0hs=0∑t⊂sfi−1,ths=1f_{i,s}= \begin{cases} 0 & h_s=0\\ \sum\limits_{t \subset s} f_{i-1,t} & h_s=1 \end{cases}
其中，hs=1h_s=1 表示 ss 合法，hs=0h_s=0 表示 ss 不合法。由于每次转移至少要改变一位，所以转移方程中的 tt 不能等于 ss。可以使用高维前缀和优化，做到时间复杂度 O(n22n)\mathcal O(n^22^n)。
求出 fw,2n−1f_{w,2^n-1} 后，只需要考虑如何把序列 bb 转回序列 aa 了。此时相当于要在 VV 个数中选出 ww 个数作为离散化前每个元素的值，方案数为 (Vw)V \choose w，因此答案等于 ∑w=1nfw,2n−1⋅(Vw)\sum\limits_{w=1}^n f_{w,2^n-1} \cdot {V \choose w}，暴力计算即可。
时间复杂度 O((n2+m)2n)\mathcal O((n^2+m)2^n)。
代码C
const int N=20,M=505,S=1<<18,mod=1e9+7;
int n,k,V,m,p[M],q[M],h[S],sum[S],f[N][S],ans;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int lowbit(int x){
	return x&-x;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod;
	}
	return res;
}
void solve(){
	cin>>n>>V>>m;
	for(int i=1;i<=m;i++) cin>>p[i]>>q[i],p[i]--,q[i]--;
	k=1<<n;
	for(int s=0;s<k;s++){
		int t=s;
		for(int i=1;i<=m;i++) if(((t>>p[i])&1)>((t>>q[i])&1)) t=t^(1<<p[i])^(1<<q[i]);
		if(lowbit(t)+t==k) h[s]=1;
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int s=0;s<k;s++) sum[s]=f[i-1][s];
		for(int p=1;p<k;p<<=1){
			for(int s=0;s<k;s++){
				if(s&p) continue;
				add(sum[s|p],sum[s]);
			}
		}
		for(int s=0;s<k;s++){
			if(h[s]==0) f[i][s]=0;
			else f[i][s]=ad(sum[s],mod-f[i-1][s]);
		}
	}
	for(int w=1;w<=n;w++){
		int pro=1;
		for(int i=V-w+1;i<=V;i++) pro=1ll*pro*i%mod;
		for(int i=1;i<=w;i++) pro=1ll*pro*ksm(i,mod-2)%mod;
		add(ans,1ll*pro*f[w][k-1]%mod);
	}
	cout<<ans<<endl;
}

ARC160F Count Sorted Arrays

题解
考虑把排列 pp 拆成 n+1n+1 个 0101 串 c0,c2,…,cnc_0,c_2,\dots,c_n，其中 ci,j=[pj≥i]c_{i,j}=[p_j\ge i]，那么排列 pp 能通过操作排好序当且仅当它拆成的 n+1n+1 个 0101 串都能通过操作排好序。
可以时刻维护每个 0101 串是否合法，把每个排列 pp 看成一个 00⋯000\cdots0 到 11⋯111\cdots1 的长度为 nn 的路径，对合法的 0101 串做一个 dp 即可得到合法的排列 pp 的数量，时间复杂度 O(nm2n)\mathcal O(nm2^n)。
感性理解，其实只有 O(n2)\mathcal O(n^2) 个操作是有效的，而其他操作都不会影响 0101 串的合法性。于是可以时刻维护 fi,jf_{i,j} 表示是否存在 0101 串 cc 满足 cmin⁡(i,j)>cmax⁡(i,j)c_{\min(i,j)} \gt c_{\max(i,j)}，只有当询问的 fai,bif_{a_i,b_i} 为真时才重新 dp 并更新所有的 fai,jf_{a_i,j} 和 fbi,jf_{b_i,j}，否则直接输出上一次询问的结果即可。
时间复杂度 O(n32n)\mathcal O(n^32^n)。
代码C
const int N=15,W=1<<15;
int n,m,V,f[N][N],g[W],h[W];
ll dp[W],ans=1;
bool get(int s,int x,int y){
	return ((s>>x)&1)>((s>>y)&1);
}
void solve(){
	cin>>n>>m,V=1<<n;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) f[i][j]=1;
	for(int s=0;s<V;s++) g[s]=s;
	for(int i=0;i<=n;i++) h[((1<<i)-1)<<(n-i)]=1;
	for(int c=1;c<=m;c++){
		int x,y;
		cin>>x>>y;
		x=(x+ans)%n,y=(y+ans+ans)%n;
		if(x>y) swap(x,y);
		if(!f[x][y]){
			cout<<ans<<endl;
			continue;
		}
		for(int i=0;i<n;i++) f[x][i]=f[i][x]=f[y][i]=f[i][y]=0;
		for(int s=0;s<V;s++){
			if(get(g[s],x,y)) g[s]^=(1<<x)^(1<<y);
			for(int i=0;i<n;i++){
				if(get(g[s],min(i,x),max(i,x))) f[x][i]=f[i][x]=1;
				if(get(g[s],min(i,y),max(i,y))) f[y][i]=f[i][y]=1;
			}
		}
		for(int s=0;s<V;s++) dp[s]=0;
		dp[0]=1;
		for(int s=1;s<V;s++){
			if(!h[g[s]]) continue;
			for(int i=0;i<n;i++) if(s&(1<<i)) dp[s]+=dp[s^(1<<i)];
		}
		ans=dp[V-1];
		cout<<ans<<endl;
	}
}

AGC008E Next or Nextnext

题解
设从 ii 指向 pip_i 所形成的图为 G1G_1，从 ii 指向 aia_i 所形成的图为 G2G_2，考虑考查 G1G_1 和 G2G_2 之间的关系。
显然 G1G_1 由若干个环组成，于是考虑 G1G_1 中的每一个环：
  • 若环上的每一个点都满足 ai=pia_i=p_i，则 G2G_2 中有一个一模一样的环；
  • 若环上的每一个点都满足 ai=ppia_i=p_{p_i} 且环长为奇数，则 G2G_2 中有一个环长相同但不一样的环；
  • 若环上的每一个点都满足 ai=ppia_i=p_{p_i} 且环长为偶数，则 G2G_2 中有两个环长为该环长度一半的环；
  • 若环上既存在满足 ai=pia_i=p_i 的点又存在满足 ai=ppia_i=p_{p_i} 的点，则 G2G_2 中会存在一棵由一个环和若干条链组成的基环内向树。
接下来考虑 G2G_2 如何推回 G1G_1。
先考虑 G2G_2 中的环。设 G2G_2 中有 cic_i 个长度为 ii 的环，枚举要合并的环的数量 2j2j：
  • 若 j≠0j \ne 0：
    • 从 cnticnt_i 个环中选出 2j2j 个环，方案数为 (cnti2j)cnt_i \choose 2j；
    • 从 2j2j 个环中选出左侧的 jj 个环，钦定左侧的环的顺序为 1∼j1\sim j，枚举右侧环的顺序，并去掉交换同一行两个环的方案，得到方案数为 (2jj)j!2j\frac{{2j \choose j}j!}{2^j}；
    • 每对环有 ii 种合并方式，方案数为 iji^j；
  • 若 ii 为奇数且 i≠1i\ne1，则每个不被合并的环也有 22 种方案，方案数为 2cnti−2j2^{cnt_i-2j}；
将每个步骤的方案数相乘即可得到这个部分的结果，将每个 jj 的结果相加即可得到每种环长的答案。
再考虑 G2G_2 中的基环内向树。不妨设基环内向树的环上的点依次为 1,2,…,m1,2,\dots,m，其中对于每个不大于 nn 的正整数 ii 都存在一条从 (i mod m)+1(i \bmod m)+1 指向 ii 的边；设挂着链的点依次为 p1,p2,…,pkp_1,p_2,\dots,p_k，挂在 pip_i 上的链的长度为 lil_i，则我们需要将 lil_i 插回 pip_i 到 p(i mod k)+1p_{(i \bmod k)+1} 之间。设 pip_i 到 p(i mod m)+1p_{(i \bmod m)+1} 之间有 ee 条边：
  • 若 e>lie>l_i，则插回的方案数为 22；
  • 若 e=lie=l_i，则插回的方案数为 11；
  • 若 e<lie<l_i，则插回的方案数为 00。
将每条链插回的方案数相乘即可得到这部分的结果，答案即为每个环和每棵基环内向树的方案数的乘积。
朴素实现的时间复杂度为 O(nlog⁡n)\mathcal O(n \log n)，精细实现可以做到 O(n)\mathcal O(n)。
代码C
const int N=1e5+5,mod=1e9+7;
int n,a[N],c[N],vis[N],ans=1,fac[N<<1],infac[N<<1];
vector <int> ve[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod; 
	}
	return res;
}
int C(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void dfs(int u,bool f,int len){
	f|=(ve[u].size()!=1);
	vis[u]=1,len++;
	if(vis[a[u]]){
		if(!f) return c[len]++,void();
		vector <int> s,p,l;
		s.pb(u),vis[u]=2;
		int v=a[u];
		while(v!=u) s.pb(v),vis[v]=2,v=a[v];
		int m=s.size();
		for(int i=0;i<m;i++){
			int u=s[i];
			if(ve[u].size()==2){
				if(vis[ve[u][0]]==2) v=ve[u][1];
				else v=ve[u][0];
				int cnt=0;
				while(1){
					vis[v]=1,cnt++;
					if(ve[v].size()==2) cout<<0<<endl,exit(0);
					if(ve[v].size()==0) break;
					v=ve[v][0];
				}
				p.pb(i),l.pb(cnt);
			}
		}
		int k=p.size();
		for(int i=0;i<k;i++){
			int e;
			if(i==0) e=p[i]+m-p[k-1];
			else e=p[i]-p[i-1];
			if(e>l[i]) add(ans,ans);
			if(e<l[i]) cout<<0<<endl,exit(0);
		}
		return;
	}
	dfs(a[u],f,len);
}
void solve(){
	cin>>n;
	fac[0]=infac[0]=1;
	for(int i=1;i<=n+n;i++) fac[i]=1ll*i*fac[i-1]%mod;
	infac[n+n]=ksm(fac[n+n],mod-2);
	for(int i=n+n-1;i>0;i--) infac[i]=1ll*(i+1)*infac[i+1]%mod;
	for(int i=1;i<=n;i++) cin>>a[i],ve[a[i]].pb(i);
	for(int i=1;i<=n;i++) if(ve[i].size()>2) cout<<0<<endl,exit(0);
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i,0,0);
	}
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=0;j+j<=c[i];j++){
			int res=1;
			if(j!=0) res=1ll*C(c[i],j+j)*C(j+j,j)%mod*fac[j]%mod*ksm((mod+1)/2,j)%mod*ksm(i,j)%mod;
			if((i&1)&&i!=1) res=1ll*res*ksm(2,c[i]-j-j)%mod;
			add(sum,res);
		}
		ans=1ll*ans*sum%mod;
	}
	cout<<ans<<endl;
}

AGC027E ABBreviate

题解
注意到，如果我们把 a\texttt a 看作 11，b\texttt b 看作 22，设 f(s)f(s) 表示字符串 ss 中所有字符所对应的数字之和对 33 取模后的值，那么每次操作不会改变 f(s)f(s)。
首先考虑字符串 ss 能不能变成单个字符 cc（s≠cs \ne c）。此时显然需要满足：
  • f(s)=f(c)f(s)=f(c)；
  • ss 中存在相邻的相同字符。
只要 ss 满足上述两个条件，那么就一定可以通过不断对 ss 中相邻的相同字符进行操作的方式使 ss 变成 cc。
接下来考虑字符串 ss 能不能变成字符串 tt（s≠ts \ne t）。此时显然需要满足：
  • f(s)=f(t)f(s)=f(t)；
  • ss 中存在相邻的相同字符；
  • 设 ∣t∣=m|t|=m，则 ss 可以被分成 m+1m+1 段子字符串 e1,e2,…,em+1e_1,e_2,\dots,e_{m+1}，其中前 ii 段均满足 f(ei)=f(ti)f(e_i)=f(t_i)，第 m+1m+1 段满足 f(em+1)=0f(e_{m+1})=0（em+1e_{m+1} 可以为空串）。
同理，只要 ss 满足上述三个条件，那么就一定可以通过相邻的相同字符调整 ss 的每一段，使 eie_i 变为 tit_i 并消去 em+1e_{m+1}。
可以在特判 ss 中不存在相邻的相同字符后 dp：设 dpidp_{i} 表示 s[1,i]s[1,i] 能变成的字符串数量，nxti,xnxt_{i,x}（1≤x≤21 \le x \le 2）表示最小的大于 ii 的下标 jj，满足 f(s[i,j−1])=xf\big(s[i,j-1]\big)=x。
初始化 f1=1f_1=1 和 nxtn+1,1=nxtn+1,2=n+2nxt_{n+1,1}=nxt_{n+1,2}=n+2，则转移方程为 dpnxti,1←dpnxti,1+dpidp_{nxt_{i,1}} \leftarrow dp_{nxt_{i,1}}+dp_i 和 dpnxti,2←dpnxti,2+dpidp_{nxt_{i,2}} \leftarrow dp_{nxt_{i,2}}+dp_i，答案即为 ∑i=2n+1dpi×[f(s[i,n])=0]\sum\limits_{i=2}^{n+1} dp_i \times \Big[f\big(s[i,n]\big)=0\Big]。
由于每个字符串 tt 都恰好对 ss 所能变成 tt 的最短前缀处贡献了 11，所以这样做是不重不漏的。时间复杂度 O(n)\mathcal O(n)。
代码C
const int N=1e5+5,mod=1e9+7;
int n,a[N],nxt[N][3],suf[N],dp[N],ans;
bool flag;
string s;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>s,n=s.size();
	for(int i=1;i<=n;i++) a[i]=s[i-1]=='a'?1:2,flag|=a[i]==a[i-1];
	if(!flag) return cout<<1<<endl,void();
	nxt[n+1][1]=nxt[n+1][2]=n+2,dp[1]=1;
	for(int i=n;i>=1;i--){
		suf[i]=(suf[i+1]+a[i])%3;
		if(a[i]==1) nxt[i][1]=i+1,nxt[i][2]=nxt[i+1][1];
		if(a[i]==2) nxt[i][1]=nxt[i+1][2],nxt[i][2]=i+1;
	}
	for(int i=1;i<=n;i++) add(dp[nxt[i][1]],dp[i]),add(dp[nxt[i][2]],dp[i]);
	for(int i=2;i<=n+1;i++) if(suf[i]==0) add(ans,dp[i]);
	cout<<ans<<endl;
}

AGC020F Arcs on a Circle

题解
将所有线段从短到长排序，考虑断环为链，以第 nn 条线段即最长的线段的左端点作为起点，将问题转化为：最长的线段的左端点位于位置 00，其余线段的左端点在 [0,c][0,c] 上随机，求 [0,c][0,c] 都被覆盖的概率。其中，以最长的线段的左端点作为起点是为了防止存在另一条更长的线段 [x,c+y][x,c+y] 覆盖了 [x,c][x,c] 和 [0,y][0,y]，对 [x,c][x,c] 和 [an,y][a_n,y] 均造成贡献的情况出现。
虽然每条线段的左端点都是在实数范围内随机的，但我们其实只关心小数部分的相对大小关系，且可以认为小数部分两两不同，因此我们可以考虑直接枚举 1∼n−11\sim n-1 的排列 pp 表示前 n−1n-1 条线段左端点小数部分的相对大小关系。于是我们现在得到了 ncnc 个整数坐标 0,1,…,nc−10,1,\dots,nc-1，第 ii 条线段的左端点只能放在 x mod n=pix \bmod n=p_i 的坐标 xx 上，我们需要求出 [0,nc][0,nc] 都被覆盖的概率。
考虑 dp：设 fi,j,Sf_{i,j,S} 表示，当前考虑到坐标 ii，前 jj 个坐标都被覆盖了，当前使用了的线段的集合为 SS 的方案数。设 i mod n=pki\bmod n=p_k，转移时选择使用或不使用第 kk 条线段即可。由于总方案数为 cn−1c^{n-1}，所以此时覆盖 [0,nc)[0,nc) 的概率等于 fnc,nc,2n−1−1cn−1\dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}}。又由于每种小数部分的相对大小关系的出现概率相等，所以答案即为每个 pp 所对应的 fnc,nc,2n−1−1cn−1\dfrac {f_{nc,nc,2^{n-1}-1}}{c^{n-1}} 的平均数。
直接计算即可。时间复杂度 O(n!n2c22n)\mathcal O(n!n^2c^22^n)。
代码C
const int N=7,C=51;
int n,c,V,a[N],p[N],rk[N];
ll ans,dp[N*C][N*C][1<<N],cnt;
void solve(){
	cin>>n>>c,V=1<<(n-1);
	for(int i=1;i<=n;i++) cin>>a[i],p[i]=i;
	sort(a+1,a+n+1);
	while(1){
		memset(dp,0,sizeof dp);
		dp[0][a[n]*n][0]=1,cnt++;
		for(int i=1;i<n;i++) rk[p[i]]=i;
		for(int i=0;i<n*c;i++){
			for(int j=i;j<=n*c;j++){
				for(int s=0;s<V;s++){
					int k=rk[i%n];
					dp[i+1][j][s]+=dp[i][j][s];
					if(k!=0&&(!(s&(1<<(k-1))))) dp[i+1][min(max(j,i+a[k]*n),c*n)][s|(1<<(k-1))]+=dp[i][j][s];
				}
			}
		}
		ans+=dp[n*c][n*c][V-1];
		if(!next_permutation(p+1,p+n)) break;
	}
	printf("%.18lf",ans*1.0/cnt/pow(c,n-1));
}

P12558 [UOI 2024] Heroes and Monsters

题解
我们把 aa 和 bb 按照从小到大的顺序排列，考虑刻画判定大小为 mm 的集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件。为了满足条件，我们可以贪心，让 SS 中的元素与 b1∼bmb_1 \sim b_m 配对，同时让不在 SS 中的元素与 bm+1∼bnb_{m+1} \sim b_n 配对。
更具体地，集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法，当且仅当：
  • 设在 SS 中的第 ii 小的元素为 axa_x，则有 ax>bia_x \gt b_i；
  • 设不在 SS 中的第 ii 小的元素为 aya_y，则有 ay<bm+ia_y \lt b_{m+i}。
于是，当 mm 确定时，我们可以设 dpi,jdp_{i,j} 表示考虑完 a1∼aia_1\sim a_i 且此时有 jj 个元素被选入 SS 中的方案数，枚举下一个元素是否选入 SS 即可得到转移方程为：
dpi,j=dpi−1,j−1×[ai>bj]+dpi−1,j×[ai<bm+j]dp_{i,j}=dp_{i-1,j-1} \times [a_i \gt b_j]+dp_{i-1,j} \times [a_i \lt b_{m+j}]
dpn,mdp_{n,m} 即为 l=ml=m 且 r=mr=m 的询问的答案。我们对每一个 0≤m≤n0 \le m \le n 都求出 dpn,mdp_{n,m} 的值，再预处理一下前缀和即可做到 O(1)\mathcal O(1) 回答单次询问。这样做的时间复杂度为 O(n3+q)\mathcal O(n^3+q)，考虑优化。
我们需要对每一个 mm 都做一次 dp 是复杂度很大的原因之一，但是 mm 是判定条件中的一个参数，有没有什么办法把判定条件中的 mm 消掉呢？
我们可以做一个变形，把判定集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件修改为：
  • 设在 SS 中的第 ii 小的元素为 axa_x，则有 ax>bia_x \gt b_i；
  • 设不在 SS 中的第 ii 大的元素为 aya_y，则有 ay<bn−i+1a_y \lt b_{n-i+1}。
显然改之后的条件和改之前的条件是等价的，我们只是把不在 SS 中的元素的枚举顺序改变了，但这样做消去了判定条件中的 mm。同时，看到这个 dp 形式，我们容易联想到分别对 aa 的前缀和后缀做一个 dp，最后把它们拼起来。
具体地，我们设 fi,jf_{i,j} 表示在只受第一个条件的限制下考虑完 a1∼aia_1 \sim a_i 且此时有 jj 个元素被选入 SS 中的方案数，gi,jg_{i,j} 表示在只受第二个条件的限制下考虑完 an∼aia_n \sim a_i 且此时有 jj 个元素没有被选入 SS 中的方案数，枚举下一个元素的状态即可得到转移方程为：
fi,j=fi−1,j+fi−1,j−1×[ai>bj]gi,j=gi+1,j−1+gi+1,j×[ai<bn−j+1]f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times[a_i \gt b_j]\\ g_{i,j}=g_{i+1,j-1}+g_{i+1,j}\times[a_i \lt b_{n-j+1}]
接下来我们考虑怎么把数组 ff 和数组 gg 拼起来。如果我们随便找一个位置 ww 将序列 aa 拆成 a1∼awa_1\sim a_w 的前缀与 aw+1∼ana_{w+1}\sim a_n 的后缀显然是有问题的——可能在 aa 的前缀中存在一个不在 SS 中的 aya_y 不满足 ay<bn−i+1a_y \lt b_{n-i+1} 的条件，也可能在 aa 的后缀中存在一个在 SS 中的 axa_x 不满足 ax>bia_x \gt b_i 的条件。
于是，我们希望对每一个集合大小 mm 找到一个位置 kk，使得 a1∼aka_1 \sim a_k 中的元素如果不在 SS 中则一定满足 ay<bn−i+1a_y \lt b_{n-i+1} 的条件，且 ak+1∼ama_{k+1} \sim a_m 中的元素如果在 SS 中则一定满足 ax>bia_x \gt b_i 的条件。
因为现在集合大小 mm 是已知的，所以我们是希望判定集合 SS 合法的条件中出现 mm 的，于是我们可以再对判定集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件做一个变形：
  • 设在 SS 中的第 ii 大的元素为 axa_x，则有 ax>bm−i+1a_x \gt b_{m-i+1}；
  • 设不在 SS 中的第 ii 小的元素为 aya_y，则有 ay<bm+ia_y \lt b_{m+i}。
我们还是只改变了元素的枚举顺序，但这样的判定条件非常有利于我们找到满足要求的位置 kk。现在，位置 kk 的要求变为了：
  • 对于 a1∼aka_1 \sim a_k 中每一个不在 SS 中的元素 aya_y，都满足 ay<bm+ia_y \lt b_{m+i}；
  • 对于 ak+1∼ana_{k+1} \sim a_n 中每一个在 SS 中的元素 axa_x，都满足 ax>bm−i+1a_x \gt b_{m-i+1}。
分析一下，如果我们有 ay<bma_y \lt b_{m} 则我们一定有 ay<bm+ia_y \lt b_{m+i}，而如果我们有 ax>bma_x \gt b_m 则我们一定有 ax>bm−i+1a_x\gt b_{m-i+1}，所以我们只需要满足 aa 的前缀都小于 bmb_m 且 aa 的后缀都大于 bmb_m 就可以满足条件了！于是我们所求的 kk 就是最大的满足 ak<bma_k \lt b_m 的位置 kk。
接下来我们只需要对于每一个 mm 找到划分位置 kk，枚举前缀中在 SS 中的元素的个数 cc，并将 l=ml=m 且 r=mr=m 的询问的答案加上 fk,c×gk+1,n−k−m+cf_{k,c} \times g_{k+1,n-k-m+c} 即可。
同样做一个前缀和即可做到 O(1)\mathcal O(1) 回答单次询问，总时间复杂度 O(n2+q)\mathcal O(n^2+q)，可以通过。
代码C
const int N=5e3+5,mod=998244353;
int n,a[N],b[N],f[N][N],g[N][N],q,sum[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	f[0][0]=1,g[n+1][0]=1;
	for(int i=1;i<=n;i++){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=i;j++){
			f[i][j]=f[i-1][j];
			if(a[i]>b[j]) add(f[i][j],f[i-1][j-1]);
		}
	}
	for(int i=n;i>=1;i--){
		g[i][0]=g[i+1][0];
		for(int j=1;j<=n-i+1;j++){
			g[i][j]=g[i+1][j];
			if(a[i]<b[n-j+1]) add(g[i][j],g[i+1][j-1]);
		}
	}
	for(int m=0;m<=n;m++){
		int k=0;
		while(k<n&&a[k+1]<b[m]) k++;
		for(int c=0;c<=m;c++) if(k>=c&&n-k-m+c>=0) add(sum[m],1ll*f[k][c]*g[k+1][n-k-m+c]%mod);
		if(m) add(sum[m],sum[m-1]);
	}
	cin>>q;
	for(int i=1,l,r;i<=q;i++){
		cin>>l>>r;
		if(l==0) cout<<sum[r]<<endl;
		else cout<<(sum[r]-sum[l-1]+mod)%mod<<endl;
	}
}

评论

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

正在加载评论...