环形划分

题目描述

有一个 \(n\) 个点的完全图，现在你要从中选取若干个三元环，使得这些三元环两两没有重边，并且使得不在三元环中的边数 \(\leq n-1\)，请构造出一种方案。

\(n\leq 1000\)

解法

我们只需要写所有满足 \(i+j+k=0\bmod n\) 的三元环 \((i,j,k)\) 即可。

显然对于一对不同的 \(i,j\)，仅有唯一的 \(k\) 满足上述条件，所以该构造不存在环与环之间的重边。

不合法的情况仅对于一对 \(i,j\)，求出的 \(k\) 与其一相等。不妨设 \(2i+j=0\bmod n\)，则 \(i,j\) 之间的边就不会被选，但是这样的情况最多有 \(n-1\) 种，因为 \(j=n\) 的时候一定没有对应的 \(i\)

如果你知道这个方法是怎么想到的，请告诉我

最小表示

题目描述

有一个长度为 \(n\) 的仅含前 \(m\) 个小写字符的串 \(S\)，你希望知道这个串本质不同的子串有多少个。

定义两个子串本质不同当且仅当他们的最小表示法不同，最小表示指将该串最靠前出现的字符都替换为字符集的第一个字符，次靠前出现的字符都替换为字符集的第二个字符，以此类推。

\(n\leq 5\cdot 10^4,m\leq 10\)

解法

显然是重题：T3字符串

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 100005;
#define int long long
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 f*x;
}
int n,a[M],p[M][26],lg[M];char s[M];
int x[M],y[M],c[M],sa[M],rk[M],dp[M][26];
vector<int> v[M];long long ans;
void init()
{
	int m=n;
	for(int i=1;i<=n;i++) c[x[i]=a[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(int k=1;k<n;k<<=1)
	{
		int num=0;
		for(int i=n-k+1;i<=n;i++) y[++num]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>k) y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[x[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		num=x[sa[1]]=1;
		for(int i=2;i<=n;i++)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n) break;
		m=num;
	}
	for(int i=1;i<=n;i++)
	{
		rk[sa[i]]=i;
		if(i>1) lg[i]=lg[i>>1]+1;
	}
	int k=0;
	for(int i=1;i<=n;i++)
	{
		int j=sa[rk[i]-1];
		if(rk[i]==1) continue;
		if(k) k--;
		while(i+k<=n && j+k<=n && a[i+k]==a[j+k]) k++;
		dp[rk[i]][0]=k;
	}
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
int lcp(int l,int r)
{
	l=rk[l];r=rk[r];
	if(l>r) swap(l,r);l++;
	int k=lg[r-l+1];
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int exlcp(int x,int y)//后缀x和后缀y的lcp
{
	int l=0,l1=v[x].size()-1,l2=v[y].size()-1;
	for(int i=0;i<l1 && i<l2;i++)
	{
		if(v[x][i]-x!=v[y][i]-y) break;//直接不等
		l++;
		int t=min(v[x][i+1]-v[x][i],v[y][i+1]-v[y][i])-1;
		int tmp=lcp(v[x][i]+1,v[y][i]+1); 
		l+=min(tmp,t); 
		if(tmp<t) break;//达不到整段 
	}
	return l;
}
bool cmp(int x,int y)
{
	int l=exlcp(x,y),c1=0,c2=0;
	if(l==n-x+1 || l==n-y+1)
		return x>y;//长度小的放前边
	if(p[x][s[x+l]-'a']==x+l) c1=n+1;
	else c1=a[x+l];
	if(p[y][s[y+l]-'a']==y+l) c2=n+1;
	else c2=a[y+l];
	//只要能决出胜负就行，因为不可能有两个特殊位置
	return c1<c2; 
}
signed main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	n=read();read();
	scanf("%s",s+1);
	//先把原串改写了
	for(int i=1;i<=n;i++)
	{
		a[i]=i-p[0][s[i]-'a'];
		p[0][s[i]-'a']=i;
	}
	init();//后缀数组
	//找到这个位置后面第一个字符
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<26;j++)
			p[i][j]=p[i+1][j];
		p[i][s[i]-'a']=i;
		for(int j=0;j<26;j++)
			if(p[i][j]) v[i].push_back(p[i][j]);
		sort(v[i].begin(),v[i].end());
		v[i].push_back(n+1);
	}
	for(int i=1;i<=n;i++) x[i]=i;
	sort(x+1,x+1+n,cmp);
	ans=1ll*n*(n+1)/2;
	for(int i=2;i<=n;i++)
		ans-=exlcp(x[i],x[i-1]);
	printf("%lld\n",ans);
}

置换矩阵

题目描述

有一个长为 \(n\) 的序列 \(a\) 和一个长度为 \(n\) 的置换 \(p\)，现在用他们生成出一个矩阵 \(A\)：

• \(A_{1,j}=a_j\)
• \(A_{i,j}=A_{i-1,p_j}(i\geq 2)\)

求 \(A\) 的行列式，答案模 \(1e9+7\)

\(n\leq 5000\)

\(\tt subtask1:\) 排列 \(p\) 的环个数 \(>1\)

\(\tt subtask2:\) \(p_1=n,p_i=i-1(i>1)\)

解法

不难发现对于 \(\tt subtask1\) 的情况可以特判掉，答案就是 \(0\)

证明略过了，因为我也不是很清楚

对于任意置换 \(p\) 都可以较为容易地转成 \(\tt subtask2\) 的循环置换，那么我们就只讨论 \(p\) 为循环置换的情况：

\[A=\left(\begin{matrix}a_0&a_1&...&a_{n-1}\\ a_{n-1}&a_0&...&a_{n-2}\\ ...&...&...&...\\ a_1&a_2&...&a_0\end{matrix}\right) \]

定义一个辅助矩阵 \(C\)：

\[C=\left( \begin{matrix} 1&1&...&1\\ 1&w_n^1&...&w_{n}^{n-1}\\ 1&w_n^2&...&w_n^{2(n-1)}\\ ..&..&...&...\\ 1&w_n^{n-1}&...&w_{n}^{(n-1)^2} \end{matrix} \right) \]

因为 \(C\) 为范德蒙德矩阵，所以可以这样算行列式：

\[\det(C)=\prod_{0\leq i<j<n}(w^j-w^i)\not=0 \]

这里给出范德蒙德行列式的证明：

\[D=\left(\begin{matrix} 1&1&1&...&1\\ x_1&x_2&x_3&...&x_n\\ ...\\ x_1^{n-1}&x_2^{n-1}&x_3^{n-1}&...&x_n^{n-1} \end{matrix}\right)\\ = \]