CF1129C Morse Code

pro:

维护一个01字符串,支持在结尾动态加字符。

每一个长度<=4的01串可以对应一个字母(有几个特例除外)

每次操作后询问，这个字符串的所有子串一共可以对应出多少种本质不同的字符串。

sol:

考虑dp。

dp[i][j]表示从i这个字符开始到当前倒数第j位这个01串，可以划分为多少不同的字符串。

每次只需要更新一下从1到i的每一个dp数组即可。

但时考虑本质不同这个问题。

显然每一种字母串对应唯一的01串。

因此我们只需要对相同的01子串只统计一次即可。

这里用SAM进行判重即可。

#include<bits/stdc++.h>

#define N 22000

#define L 20000

#define eps 1e-7

#define inf 1e9+7

#define db double

#define ll long long

#define ldb long double

using namespace std;

inline int read()

{

	char ch=0;

	int x=0,flag=1;

	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*flag;

}

const ll mo=1e9+7;

int f[N],id[N],dp[N][8];

int root=1,size=1,last=1;

struct node{int pos,len,lnk,nxt[2];}s[N];

void build(int k)

{

	int cur=++size,p=last;last=cur;

	s[cur].len=s[p].len+1;s[cur].pos=s[cur].len;

	while(p&&!s[p].nxt[k])s[p].nxt[k]=cur,p=s[p].lnk;

	if(!p){s[cur].lnk=root;return;}

	int q=s[p].nxt[k];

	if(s[q].len==s[p].len+1){s[cur].lnk=q;return;}

	else

	{

        int clone=++size;

        s[clone]=s[q];s[clone].len=s[p].len+1;

		while(p&&s[p].nxt[k]==q)s[p].nxt[k]=clone,p=s[p].lnk;

        s[q].lnk=s[cur].lnk=clone;

    }

}

int main()

{

	srand(time(0));

	int n=read(),ans=0;

	for(int i=1;i<=n;i++)f[i]=read(),build(f[i]);

	for(register int o=1;o<=n;o++)

	{

		id[o]=root;

		for(register int i=1;i<o;i++)

		{

			for(register int j=4;j>=1;j--)dp[i][j]=dp[i][j-1];dp[i][0]=0;

			for(register int j=1;j<=4;j++)if(o-i+1>=j)

			{

				if(j==4)

				{

					if(f[o-3]==0&&f[o-2]==0&&f[o-1]==1&&f[o]==1)continue;

					if(f[o-3]==0&&f[o-2]==1&&f[o-1]==0&&f[o]==1)continue;

					if(f[o-3]==1&&f[o-2]==1&&f[o-1]==1&&f[o]==0)continue;

					if(f[o-3]==1&&f[o-2]==1&&f[o-1]==1&&f[o]==1)continue;

				}

				dp[i][0]=(dp[i][0]+dp[i][j])%mo;

			}

			int x=id[i];

			if(x!=-1){if(s[x].nxt[f[o]])x=s[x].nxt[f[o]];else x=-1;}

			if(x==-1||o==s[x].pos)ans=(ans+dp[i][0])%mo;id[i]=x;

		}

		dp[o][0]=dp[o][1]=1;

		int x=id[o];

		if(x!=-1){if(s[x].nxt[f[o]])x=s[x].nxt[f[o]];else x=-1;}

		if(x==-1||o==s[x].pos)ans=(ans+dp[o][0])%mo;id[o]=x;

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

	}

	return 0;

}

巴特西

CF1129C Morse Code

最新文章

热门文章