#17 CF715E & CF1375H & CF1483F

Complete the Permutations

题目描述

点此看题

解法

找到快速计算相似度的方式是做这道题的前提，发现相似度就等于 \(n-\)置换环个数。其中置换环的含义是：对于所有 \(i\)，连边 \(p_i\rightarrow q_i\) 所形成的环。

我们并不关心排列长什么样子，我们只关心图上的每一条边，可以按照下列方法把边分类：① \(a\rightarrow b\)；② \(a\rightarrow 0\)；③ \(0\rightarrow b\)；④ \(0\rightarrow 0\)；

首先考虑简化问题，对于 ① 边，可以把已知的 \(a\rightarrow b,b\rightarrow c\) 拼成 \(a\rightarrow c\)，这样场上可能会剩下若干条已经确定的链，和 \(cnt\) 个已经确定的环。对于 ①② 边，可以把 \(a\rightarrow b,b\rightarrow 0\) 合并成 \(a\rightarrow 0\)；对于 ①③ 边，可以把 \(0\rightarrow a,a\rightarrow b\) 合并成 \(0\rightarrow b\)

上述的合并都是不需要计算方案数的，接下来考虑更复杂的合并：

• 对于 ② 边，可以自身合并，得到 ② 边；也可以和 ④ 边合并，得到 ④ 边。
• 对于 ③ 边，可以自身合并，得到 ③ 边；也可以和 ④ 边合并，得到 ④ 边。
• 对于 ④ 边，可以自己构成环；也可以和已经存在的 ① 链构成环。

关键的 \(\tt observation\) 是：在合成环之前，④ 边的数量不会改变，所以我们可以考虑下面的计数顺序：

• 对于 ① 链 \(a\rightarrow b\)，我们把场上还剩下的 \(a,b\) 给一个新的标号 \(c\)，以后的合并都通过 \(c\) 来完成，最后再把 \(c\) 替换成 \(a\rightarrow b\) 链即可，这样可以排除掉 ① 链的影响（这步很重要，但貌似网上的题解没有说清楚）
• ② 边自己构成环，或者是转化为 ④ 边。
• ③ 边自己构成环，或者是转化为 ④ 边。
• ④ 边自己构成环，此时的方案数计算不受前面任何操作的影响。

那么三步计数可以看成独立的，我们用生成函数来标记置换环个数，首先写出 ② 边合并的生成函数，设 \(n_2/n_3\) 分别表示 ②③ 类边的数量，\(m\) 表示 ④ 类边的数量：

\[[x^k]F_2(x)=\sum_{i=k}^{n_2}{n_2\choose i}\cdot {i\brack k}\cdot (n_2+m-i-1)^{\underline {n_2-i}} \]

解释一下上式的含义：我们考虑构造 \(k\) 个置换环，先选出 \(i\) 个点 \({n_2\choose i}\)，然后就是 \(i\) 个点构成 \(k\) 个圆排列的方案数 \({i\brack k}\)，剩下的点可以自己合并也可以合并到 ④ 上去，第一个合并的方案数是 \(n_2+m-i-1\)，每合并一次合并的选择就减少 \(1\)，所以呈现出来是下降幂的形式。类似可以写成 ③ 边合并的生成函数：

\[[x^k]F_3(x)=\sum_{i=k}^{n_3}{n_3\choose i}\cdot {i\brack k}\cdot (n_3+m-i-1)^{\underline {n_3-i}} \]

现在写出 ④ 边合并的生成函数，我们先构成圆排列，然后分配标号（可分配的标号个数就是 \(m\)）：

\[[x^k]F_4(x)={m\brack k}\cdot m! \]

如果你完全理解了计数顺序，那么就知道这三个生成函数卷起来就是最终的生成函数。设得到的函数时 \(G(x)\)，相似度为 \(i\) 的方案数就是 \([x^{n-i-cnt}]G(x)\)，暴力实现卷积和第一类斯特林数，时间复杂度 \(O(n^2)\)

#include 
const int M = 255;
#define int long long
const int MOD = 998244353;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,cnt,a[M],p1[M],p2[M],fa[M],v1[M],v2[M];
int fac[M],inv[M],f[M],g[M],h[M],s[M][M];
int find(int x)
{
	return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void init(int n)
{
	fac[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
	s[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1))%MOD;
}
int C(int n,int m)
{
	if(n=0?f[n-i-cnt]:0);
}

Set Merging

题目描述

点此看题

解法

感觉越来越思考不动了，感觉自己又没有见过什么套路，脑子还不好用 \(...\)

一眼 \(2\cdot 2^{20}=2\cdot 2^{12}\cdot 2^{8}\approx 2.2\cdot 10^6\)，鉴定为：值域分块。

考虑把值域划分为 \(\frac{n}{B}\) 个块长为 \(B\) 的块，我们把值域块中的元素对应到原序列中，得到 \(p_1,p_2...p_B\) 。对于一个块，如果我们能够处理出 \(\forall l,r\in\{p_1,p_2...p_B\}\)，原序列区间 \([l,r]\) 中所出现元素的集合，那么对于一个询问，我们可以在每个块中取出区间 \([ql,qr]\) 对应的集合，由于块间有天然偏序关系，可以直接合并，询问就只需要划分 \(q\cdot \frac{n}{B}\) 次了。

考虑对于每个块分别处理信息，由于每个块的信息有 \(O(B^2)\) 个，而我们需要的询问次数就是 \(\frac{n}{B}\cdot B^2\)，是不允许带上其他东西的。所以我们考虑值域分治，因为值域分治如果配合上平方是不会让复杂度升级的。

具体来说，我们递归获得 \([l,mid],[mid+1,r]\) 的区间信息，然后暴力枚举 \([l,r]\) 的所有区间，可以利用 \([l,mid],[mid+1,r]\) 中的子序列合并得到当前的子序列，初始时我们传入 \([1,B]\)，复杂度可以这样分析：

\[F(n)=\frac{n^2}{2}+2F(\frac{n}{2})\rightarrow F(n)=n^2 \]

那么处理的复杂度就做到了 \(\frac{n}{B}\cdot B^2=nB\)，总询问次数 \(n(B+\frac{q}{B})\)，取 \(B=\sqrt q\) 就可以得到 \(2n\sqrt q\) 的询问次数。由于需要二分，时间复杂度是 \(O(n\sqrt q\log n)\)

总结

值域分块带有天然的偏序关系，在偏序关系限制比较严格的时候可以尝试使用。

分治法处理平方信息时，暴力合并上来可以让复杂度不升级（处理 \(n^2\) 的信息只需要 \(n^2\) 的时间）

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int M = 1<<22;
#define V vector
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,q,B,a[M],ans[M],c[M],d[M];
int comb(int x,int y)
{
	if(!x || !y) return x+y;
	m++;c[m]=x;d[m]=y;return m;
}
struct node
{
	V p;vector id;
	void init(int x)
	{
		p.resize(x);id.resize(x);
		for(int i=0;ip.back()) return 0;
		l=lower_bound(p.begin(),p.end(),l)-p.begin();
		r=upper_bound(p.begin(),p.end(),r)-p.begin()-1;
		return l>r?0:id[l][r-l];
	}
	node upd(const node &x,const node &y)
	{
		init(x.p.size()+y.p.size());
		merge(x.p.begin(),x.p.end(),y.p.begin(),y.p.end(),p.begin());
		for(int i=0;ir) return node(0);
	if(l==r) return node(l);
	int mid=(l+r)>>1;node tmp;
	return tmp.upd(solve(l,mid),solve(mid+1,r));
}
signed main()
{
	n=read();m=n;q=read();B=1<<8;
	for(int i=1;i<=n;i++) a[read()]=i;
	for(int i=0;i<=n/B;i++)
		t[i]=solve(i*B+1,min(n,(i+1)*B));
	for(int i=1;i<=q;i++)
	{
		int l=read(),r=read();
		for(int j=0;j<=n/B;j++)
			ans[i]=comb(ans[i],t[j].ask(l,r));
	}
	printf("%d\n",m);
	for(int i=n+1;i<=m;i++)
		printf("%d %d\n",c[i],d[i]);
	for(int i=1;i<=q;i++)
		printf("%d ",ans[i]);
}

Exam

题目描述

点此看题

解法

考虑枚举 \(s_i\)，然后寻找所有可能的 \(s_j\)

我们从左往右枚举 \(s_i\) 的右端点，找到左端点最靠左，并且是它子串的 \(s_j\)，它是可能成为答案的。我们把所有可能的 \(j\) 都记录下来，并且记录下对应的左端点 \(L_i\)

考虑如何处理可能答案之间的包含关系，考虑这样一种特例：aa、aab、aaaab

在 \(s_3\) 中，aab 包含了 aa，但是我们如何判断呢？发现 \(L_4=L_3=3\) 说明了它们具有包含关系，所以我们从右往左扫描，\(L\) 递减的点才是有效的，其它都应该是被淘汰的。

此外我们应该要求 \(s_j\) 在 \(s_i\) 中出现的每一个位置都不被其它串包含，所以 \(s_j\) 在 \(s_i\) 中的出现次数应该等于在有效点集合中的出现次数，不难发现这样的判断是充分的。

考虑 \(s_j\) 在 \(s_i\) 中的出现次数，应该用树状数组加 \(\tt AC\) 自动机来维护，一开始把 \(s_i\) 中的所有前缀在自动机上标记，然后用树状数组统计 \(\tt fail\) 树内有多少被标记点即可，时间复杂度 \(O(|S|\log |S|)\)

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int M = 1000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,cnt,ans,out[M],ch[M][26],mx[M],id[M];
int dfn[M],fa[M],b[M],L[M],np[M],ln[M],c[M],ed[M];
vector g[M];string s[M];
void add(string &s,int x)
{
	int p=0;ln[x]=s.length();
	for(int i=0;i q;
	for(int i=0;i<26;i++)
		if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		mx[u]=max(mx[u],mx[fa[u]]);
		if(!id[u]) id[u]=id[fa[u]];
		for(int i=0;i<26;i++)
			if(ch[u][i]) fa[ch[u][i]]=ch[fa[u]][i],q.push(ch[u][i]);
			else ch[u][i]=ch[fa[u]][i];
	}
	for(int i=1;i<=cnt;i++)
		g[fa[i]].push_back(i);
	cnt++;dfs(0);
}
void add(int x,int f)
{
	for(int i=x;i<=cnt;i+=i&(-i)) b[i]+=f;
}
int ask(int x)
{
	int r=0;
	for(int i=x;i>0;i-=i&(-i)) r+=b[i];
	return r;
}
int get(int x)
{
	return ask(out[ed[x]])-ask(dfn[ed[x]]-1);
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
		cin>>s[i],add(s[i],i);
	build();
	for(int i=1;i<=n;i++)
	{
		vector vc;
		for(int j=0,p=0;j=0;j--)
		{
			if(L[j]<=j && L[j]