mcfx's blog - 字符串

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

2017-02-20T22:27:00+08:00

##Description
幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的2600岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 
粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 
这时幽香发现了一件非常有趣的事情，太阳花田有n块空地。在过去，幽香为了方便，在这n块空地之间修建了n-1条边将它们连通起来。也就是说，这n块空地形成了一个树的结构。 
有n个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺，他们选择了c中颜色的衣服，每种颜色恰好可以用一个0到c-1之间的整数来表示。并且每个人都站在一个空地上，每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。 
粉丝们策划的一个节目是这样的，选中两个粉丝A和B（A和B可以相同），然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来（包括端点），幽香就能看到一个长度为A到B之间路径上的所有粉丝的数目（包括A和B）的颜色序列。一开始大家打算让人一两个粉丝（注意：A,B和B,A是不同的，他们形成的序列刚好相反，比如红绿蓝和蓝绿红）都来一次，但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。 
于是他们想要问题，在这个树上，一共有多少可能的不同的颜色序列（子串）幽香可以看到呢？ 
太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。

###Input
第一行两个正整数n,c。表示空地数量和颜色数量。 
第二行有n个0到c-1之间，由空格隔开的整数，依次表示第i块空地上的粉丝的衣服颜色。（这里我们按照节点标号从小到大的顺序依次给出每块空地上粉丝的衣服颜色）。 
接下来n-1行，每行两个正整数u,v，表示有一条连接空地u和空地v的边。

###Output
一行，输出一个整数，表示答案。

###Sample Input
7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5

###Sample Output
30

###HINT
对于所有数据，1<=n<=100000, 1<=c<=10。 
对于15%的数据，n<=2000。 
另有5%的数据，所有空地都至多与两个空地相邻。 
另有5%的数据，除一块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。 
另有5%的数据，除某两块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。

###Solution
考虑一条从u到v的路径上的字符串，如果在两端不断加节点，一定可以扩充成一条两个度数为1的节点间的路径上的子串。
那么显然有一种方法是把20个节点两两间的字符串建成广义SAM，然后直接统计，但是这样时间、内存都会超。
建广义SAM时，每次会把last设为初始节点，那么对于这道题，也可以类似优化。
把每个度数为1的节点作为根dfs，每次dfs时记下当前last，然后在处理完一棵子树后还原last。

###Code
```c++
#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>

typedef long long ll;

#define N 2000010

struct node
{
	int ma,inc;ll cnt;
	node*link,*nxt[10];
}pool[N*2],*pm=pool+1,*start=pool;

namespace _A{node*lst,*cur,*p,*q,*sq;}
void add(int t)
{
	using namespace _A;
	cur=pm++;
	cur->ma=lst->ma+1;
	for(p=lst;p&&!p->nxt[t];p=p->link)p->nxt[t]=cur;
	if(!p){cur->link=start;goto naive;}
	q=p->nxt[t];
	if(p->ma+1==q->ma){cur->link=q;goto naive;}
	sq=pm++;
	sq->ma=p->ma+1;
	memcpy(sq->nxt,q->nxt,sizeof(q->nxt));
	for(;p&&p->nxt[t]==q;p=p->link)p->nxt[t]=sq;
	sq->link=q->link;
	q->link=sq;
	cur->link=sq;
	naive:lst=cur;
}

struct edge
{
	int to;edge*ne;
}_e[200000],*e=_e,*p[100001];

inline void add(int a,int b)
{
	*e=(edge){b,p[a]};p[a]=e++;
}

int c[100001],deg[100001];

void dfs(int x,int fa)
{
	add(c[x]);
	node*t=_A::lst;
	for(edge*i=p[x];i;i=i->ne)
		if(i->to^fa)
		{
			_A::lst=t;
			dfs(i->to,x);
		}
}

node*q[N*2];

int main()
{
	int n,x,y;
	scanf("%d%*d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",c+i);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		deg[x]++;
		deg[y]++;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)if(deg[i]==1)
		_A::lst=start,dfs(i,0);
	for(node*i=pool;i<pm;i++)
		for(int j=0;j<10;j++)if(i->nxt[j])i->nxt[j]->inc++;
	int qe=0;
	for(node*i=pool;i<pm;i++)
		if(!i->inc)i->inc=1e9,q[qe++]=i;
	for(int i=0;i<qe;i++)
		for(int j=0;j<10;j++)if(q[i]->nxt[j])if(!--q[i]->nxt[j]->inc)
			q[i]->nxt[j]->inc=1e9,q[qe++]=q[i]->nxt[j];
	for(int i=qe-1;~i;i--)
	{
		for(int j=0;j<10;j++)if(q[i]->nxt[j])q[i]->cnt+=q[i]->nxt[j]->cnt;
		q[i]->cnt++;
	}
	printf("%lld",start->cnt-1);
}
```

BZOJ 3160: 万径人踪灭

2017-01-20T22:21:00+08:00

###Description
略。见[BZOJ3160][1]

###Solution
对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出
考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$
如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1

###Code
```c++
#include<bits/stdc++.h>
typedef double lf;

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)

inline int mod(int x,int y){if(x>=y)return x-y;return x;}

#define N 524288

struct num
{
	lf r,i;
	num(){r=i=0;}
	num(lf x){r=x,i=0;}
	num(lf x,lf y){r=x,i=y;}
	num(const num &x){r=x.r,i=x.i;}
	inline num& operator +=(const num &x){r+=x.r,i+=x.i;}
	inline num& operator -=(const num &x){r-=x.r,i-=x.i;}
	inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;}
	inline num operator +(const num &x){num t=*this;t+=x;return t;}
	inline num operator -(const num &x){num t=*this;t-=x;return t;}
	inline num operator *(const num &x){num t=*this;t*=x;return t;}
};

int id[N];
num tx[N],mf[N];

inline void init_id(int y)
{
	fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1;
}

#define idft(a,b) dft(a,b,1)

inline void dft(num *s,int n,bool II=0)
{
	fo0(i,1<<n)tx[i]=s[id[i]];
	fo1(p,n)
	{
		lf tmp=M_PI*2/(1<<p);
		if(II)tmp=-tmp;
		num t0(1),t1(cos(tmp),sin(tmp));
		fo0(i,1<<p-1)mf[i]=t0,t0*=t1;
		num X,Y;
		for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir)
		{
			X=tx[i|j],Y=tx[i|j|ir]*mf[j];
			tx[i|j]=X+Y,tx[i|j|ir]=X-Y;
		}
	}
	fo0(i,1<<n)s[i]=tx[i];
}

#define N2 100010

struct node
{
	int len,cnt;
	node *nxt[2],*fail;
}t[N2+2],*tm=t+2;

inline void build(char *s,int n)
{
	t[0].len=0,t[1].len=-1;
	node *cur=t+1,*tmp,*t2;
	t[0].fail=t+1;
	for(int i=0;i<n;i++)
	{
		char u=s[i]-'a';
		for(;s[i]!=s[i-1-cur->len];cur=cur->fail);
		if(cur->nxt[u])
			cur=cur->nxt[u],cur->cnt++;
		else
		{
			tmp=cur->nxt[u]=tm++;
			tmp->len=cur->len+2;
			tmp->cnt=1;
			if(tmp->len==1)
				tmp->fail=t;
			else
			{
				for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail);
				tmp->fail=t2->nxt[u];
			}
			cur=tmp;
		}
	}
}

inline void count()
{
	for(node *x=tm-1;x>=t;x--)
		if(x->fail)x->fail->cnt+=x->cnt;
}

#define P 1000000007

inline int cnt()
{
	int ans=0;
	for(node *x=tm-1;x>t+1;x--)
		ans=mod(ans+x->cnt,P);
	return ans;
}

char s[100000];
num p[N];
int po[100001];

int main()
{
	scanf("%s",s);
	int n=strlen(s);
	fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P);
	int y=0;
	while((1<<(y+1))<n*4)y++;y++;
	fo0(i,n)p[i]=s[i]=='a'?1:-1;
	init_id(y);
	dft(p,y);
	fo0(i,1<<y)p[i]*=p[i];
	idft(p,y);
	lf t=1.0/(1<<y);
	int ans=0;
	fo0(i,n*2-1)
	{
		int cnt=round(p[i].r*t);
		cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2;
		ans=mod(ans+po[cnt],P);
	}
	build(s,n);
	count();
	printf("%d",mod(ans+P-cnt(),P));
}
```

[1]: http://www.lydsy.com/JudgeOnline/problem.php?id=3160

BZOJ 1009: [HNOI2008]GT考试

2016-09-09T20:13:00+08:00

###Description
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0

###Input
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

###Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

###Sample Input
4 3 100
111

###Sample Output
81

###Solution
我们把不吉利的数字用s表示，用f[i][j]表示n[i]匹配到s[j]的情况数，则可以用一个转移矩阵a通过f[i-1][j]求出f[i][j]
a[i][j]表示在s中匹配了i位时，在后面添数，有多少种情况匹配到j位，也就是指s的前i位后面添数后最长的公共前后缀长度为j的情况数
kmp预处理，然后对于每个i，枚举添加的数，再仿照kmp进行处理，即可求出转移矩阵
矩阵快速幂优化就可以过了，时间复杂度$$O(logN*M^3)$$

###Code
```c++
#include<cstdio>
 
struct _matrix
{
    int s[21][21],a,b;
    _matrix()
    {
        for(int i=0;i<21;i++)
            for(int j=0;j<21;j++)
                s[i][j]=0;
    }
}temp;
 
int mod;
 
void mul(_matrix &x,_matrix y)
{
    for(int i=0;i<x.a;i++)
        for(int j=0;j<y.b;j++)
        {
            temp.s[i][j]=0;
            for(int k=0;k<x.b;k++)
                temp.s[i][j]+=x.s[i][k]*y.s[k][j];
            temp.s[i][j]%=mod;
        }
    temp.a=x.a;
    temp.b=y.b;
    x=temp;
}
 
int m[21],n,f[21];
 
int main()
{
    int mm;
    scanf("%d%d%d",&n,&mm,&mod);
    char t[20];
    scanf("%s",t);
    for(int i=0;i<mm;i++)m[i+1]=t[i]-48;
    f[1]=0;
    for(int i=2;i<=mm;i++)
    {
        int t=i-1;
        while(t!=0&&m[f[t]+1]!=m[i])t=f[t];
        if(t==0)
        {
            if(m[1]==m[i])
                f[i]=1;
            else
                f[i]=0;
        }
        else
        {
            f[i]=f[t]+1;
        }
    }
    _matrix a;
    a.a=mm+1;
    a.b=mm+1;
    a.s[0][0]=9,a.s[0][1]=1;
    for(int i=1;i<mm;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(m[i+1]==j)
            {
                a.s[i][i+1]++;
                continue;
            }
            int t=i;
            while(t!=0&&m[f[t]+1]!=j)t=f[t];
            if(t==0)
            {
                if(m[1]==j)
                    a.s[i][t+1]++;
                else
                    a.s[i][0]++;
            }
            else
                a.s[i][f[t]+1]++;
        }
    }
    _matrix b;
    b.a=1;
    b.b=mm+1;
    b.s[0][0]=9;
    b.s[0][1]=1;
    int ans=0,to=n-1,no=1;
    while(no<to)
    {
        if(to&no)mul(b,a);
        mul(a,a);
        no<<=1;
    }
    for(int i=0;i<mm;i++)ans+=b.s[0][i];
    printf("%d\n",ans%mod);
    return 0;
}
```