[BZOJ4180] 字符串计数

膜一发KsCla巨佬
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+10;

struct __SAM {

	int lst,tot,ch[N][4],prt[N],mxl[N];

	void init() {

		memset(ch[1],0,sizeof ch[1]);

		lst=tot=1;

	}

	void extend(int c) {

		int p=lst,x=lst=++tot; mxl[x]=mxl[p]+1;

		while(p&&!ch[p][c]) ch[p][c]=x,p=prt[p];

		if(!p) prt[x]=1;

		else {

			int q=ch[p][c];

			if(mxl[q]==mxl[p]+1) prt[x]=q;

			else {

				int k=++tot;

				mxl[k]=mxl[p]+1; prt[k]=prt[q];

				prt[q]=prt[x]=k;

				memcpy(ch[k],ch[q],sizeof ch[q]);

				while(ch[p][c]==q) ch[p][c]=k,p=prt[p];

			}

		}

	}

} SAM;

ll n;

char str[N]; queue<int> Q;

int m,dep[N]; bool vis[N];

struct Mtrx {

	ll a[4][4];

	ll*operator[](const int&x) {return a[x];}

	const ll*operator[](const int&x) const{return a[x];}

	ll getMin() {

		ll ans=2e18;

		for(int i=0; i<m; ++i) ans=*min_element(a[i],a[i]+m);

		return ans;

	}

	Mtrx getPow(ll y) {

		if(y==1) return *this;

		Mtrx c=*this,x=c; y--;

		for(; y; y>>=1,x=x*x) if(y&1) c=c*x;

		return c;

	}

	Mtrx operator*(const Mtrx&b) const{

		Mtrx c; memset(&c,0x3f,sizeof c);

		for(int i=0; i<m; ++i) for(int k=0; k<m; ++k)

			for(int j=0; j<m; ++j) c[i][j]=min(c[i][j],a[i][k]+b[k][j]);

		return c;

	}

} E;

inline void bfs(int T) {

	memset(vis,0,sizeof vis);

	dep[SAM.ch[1][T]]=1;

	vis[SAM.ch[1][T]]=1;

	Q.push(SAM.ch[1][T]);

	while(Q.size()) {

		int x=Q.front(); Q.pop();

		for(int i=0,y; i<m&&(y=SAM.ch[x][i],true); ++i)

			if(y&&!vis[y]) Q.push(y),vis[y]=1,dep[y]=dep[x]+1;

			else E[T][i]=min(E[T][i],(ll)dep[x]);

	}

}

int main() {

	SAM.init();

	scanf("%lld%s",&n,str);

	for(int i=0; str[i]; ++i) {

		SAM.extend(str[i]-'A');

		m=max(m,str[i]-'A'+1);

	}

	memset(&E,0x3f,sizeof E);

	for(int i=0; i<m; ++i) bfs(i);

	ll l=0,r=1e18,mid,ans=0;

	while(l<=r) {

		mid=(l+r)>>1;

		if(E.getPow(mid).getMin()<n) l=mid+1;

		else ans=mid,r=mid-1;

	}

	printf("%lld\n",ans);

	return 0;

}
巴特西

[BZOJ4180] 字符串计数

最新文章

热门文章
