RikkawithNewYear'sParty

NC213950. RikkawithNewYear'sParty

描述

Rikka is now organizing a new year's party for the algorithm association. She has invited n actors from 26 different groups, represented by lowercase letters. Rikka wants to select some actors among them for the opening show.
Now, the n actors are in a row. The i-th actor is from the $s_i$ -th group. Rikka decides to choose a non-empty range $[l,r]\ (1 \leq l \leq r \leq n)$ and lets all actors in this range join in the opening show.
Rikka has prepared 26 different actions. Suppose the range [l,r] has been determined, the opening show will proceed in the following way:

The actors will play in order. The l-th actor will play at first and the r-th will play at last;
Suppose now the i-th player is going to play. He/she will decide his/her action in the following way: If there is a player j which plays before him/her and is also from group $s_i$ , the i-th player will choose the same action as the player j. Otherwise, he/she will choose the first action (the action with the smallest index) which has not been chosen by anyone before.

For example, if 5 players from groups "abacb" are selected, they will chose actions 1,2,1,3,2 respectively.
Rikka finds that different ranges may sometimes result in the same show. For example, if there are 6 players and they are from "abacbc" respectively, range [1,3] and [4,6] will result in the same show.

Given string s, Rikka wants you to calculate the number of different possible shows.

Two shows are different if and only if they contain different numbers of actions or there exists an index i such that the i-th actions of these two shows are different;
A show is possible if and only if it can be produced by some range [l,r] of s.

输入描述

The first line contains a single integer , the number of actors.

The second line contains a lowercase string s of length n.  represents the group of the i-th actor.

输出描述

Output a single line with a single integer, the number of different possible shows.

示例1

输入:

5
ababc

输出:

说明:

There are 7 different possible shows:
1. Action 1, corresponding to range [1,1], [2,2], [3,3], [4,4], [5,5].
2. Actions 1,2, corresponding to range [1,2],[2,3],[3,4],[4,5].
3. Actions 1,2,1, corresponding to range [1,3], [2,4].
4. Actions 1,2,3, corresponding to range [3,5].
5. Actions 1,2,1,2, corresponding to range [1,4].
6. Actions 1,2,1,3, corresponding to range [2,5].
7. Actions 1,2,1,2,3, corresponding to range [1,5].

示例2

输入:

6
abacbc

输出:

示例3

输入:

11
ababcdcefef

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 1751ms, 内存消耗: 43260K, 提交时间: 2020-11-22 12:38:08

#include<bits/stdc++.h>

#define N 200005
#define Mo 998244353
#define Seed 23333

using namespace std;

char c[N];

int i,j,m,n,p,k,Next[N][26],pos[N],a[N],Hash[N],Del[N][30],sa[N],Pow[N];

vector<int>v[N];

int TheNum(int x,int y)
{
	int i;
	for (i=0;i<=26;++i) if (v[x][i]==y) return 0;
	return a[y];
}

int getHash(int l,int r)
{
	int s=(Hash[r]-1ll*Hash[l-1]*Pow[r-l+1]%Mo+Mo)%Mo;
	int w=upper_bound(v[l].begin(),v[l].end(),r)-v[l].begin();
	s=(s-1ll*Del[l][w-1]*Pow[r-v[l][w-1]]%Mo+Mo)%Mo;
	return s;
}
int lcp(int a,int b)
{
	if (a==4&&b==3)
		a=4;
	int l=0,r=min(n-a+1,n-b+1)+1,mid=0;
	while ((l+r)>>1!=mid)
	{
		mid=(l+r)>>1;
		if (getHash(a,a+mid-1)==getHash(b,b+mid-1)) l=mid;
		else r=mid;
	}
	return l;
}

int cmp(int a,int b)
{
	int len=lcp(a,b);
	if (len==n-a+1||len==n-b+1) return a>b;
	return TheNum(a,a+len)<TheNum(b,b+len);
}

int main()
{
	scanf("%d",&n);
	scanf("%s",c+1);
	for (i=0;i<26;++i) Next[n+1][i]=n+1;
	for (i=n;i>=1;--i)
	{
		for (j=0;j<26;++j) Next[i][j]=Next[i+1][j];
		Next[i][c[i]-'a']=i;
	}
	Pow[0]=1; for (i=1;i<=2*n;++i) Pow[i]=1ll*Pow[i-1]*Seed%Mo;
	for (i=0;i<26;++i) pos[i]=0;
	for (i=1;i<=n;++i) 
	{
		 int w=c[i]-'a';
		 if (pos[w]==0) a[i]=0;
		 else a[i]=i-pos[w];
		 pos[w]=i;	
	}
	for (i=1;i<=n;++i) Hash[i]=(1ll*Hash[i-1]*Seed%Mo+a[i])%Mo;
	for (i=1;i<=n;++i)
	{
		v[i].push_back(0);
		for (j=0;j<26;++j) v[i].push_back(Next[i][j]);
		sort(v[i].begin(),v[i].end());
		for (j=1;j<=26;++j) Del[i][j]=(1ll*Del[i][j-1]*Pow[v[i][j]-v[i][j-1]]%Mo+a[v[i][j]])%Mo;
	}
	for (i=1;i<=n;++i) sa[i]=i;
	sort(sa+1,sa+n+1,cmp);
	long long ans=0;
	for (i=1;i<=n;++i) 
	{
		ans+=n-sa[i]+1;
		if (i>1) ans-=lcp(sa[i-1],sa[i]);
	}
	printf("%lld\n",ans);
}