Description

Solution

T1 game

咕咕咕

T2 string

fail树各个节点的深度之和怎么求？

我们考虑每个前缀的深度是什么

发现这个值就相当于有多少个前缀等于它的后缀
所以有个思路就是考虑一对相同子串的贡献

假设这两个子串是\(S[x..y]\)和\(S[l..r]\)

那么包含\(S[x..r]\)的fail树有\(n-r+1\)个，所以贡献就是\(n-r+1\)
发现上面的可以转化为求\(\sum f_i\)，其中\(f_i\)表示\(S[1..i]\)包含的相等子串的数量
最后，考虑\(f_i\)比\(f_{i-1}\)多了多少，发现其实就是所有以\(S_i\)结尾的后缀的贡献总和

考虑计算这个贡献总和

这些串对应的节点实际上组成了parent树上从np到root的一条路径

求路径和的话，可以用有根树LCT（不用makeroot）

每个节点的贡献？

\[(step[x]-step[fail[x]])*(cnt[x]-1)
\]

\(cnt[x]\)表示的是这个节点的\(right\)集合大小
LCT需要做什么？

支持单点修改\(step[x]-step[fail[x]]\)的值，以及维护子树和

支持修改整条链（都是一条到根的路径）的\(cnt\)值

支持求一条到根路径的贡献和

#include<bits/stdc++.h>

#define ll long long

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

#define get(x) (c[fa[x]][1]==x)

const int MN=2e5+5,MX=4e5+5,mod=1e9+7;

int fail[MX],ss[MX][26],step[MX];

int last=1,cnt=1;

ll ans=0,tmp=0;

int val[MX],lazy[MX];

ll X[MX],siz[MX];

int fa[MX],c[MX][2];

inline void upd(int x,int v)

{

    if(!x)return;val[x]+=v;lazy[x]+=v;

    X[x]=(X[x]+1ll*siz[x]*v%mod)%mod;

}

inline void up(int x)

{

    siz[x]=(siz[c[x][0]]+siz[c[x][1]]+step[x]-step[fail[x]])%mod;

    X[x]=(X[c[x][0]]+X[c[x][1]]+1ll*(val[x]-1)*(step[x]-step[fail[x]])%mod)%mod;

}

inline void down(int x){if(!lazy[x])return;upd(c[x][0],lazy[x]);upd(c[x][1],lazy[x]);lazy[x]=0;}

inline bool nrt(int x){return c[fa[x]][1]==x||c[fa[x]][0]==x;}

inline void rotate(int x)

{

    int y=fa[x],z=fa[y],l=get(x),r=l^1;if(nrt(y))c[z][get(y)]=x;fa[x]=z;

    fa[c[x][r]]=y;c[y][l]=c[x][r];fa[y]=x;c[x][r]=y;up(y);

}

inline void Splay(int x)

{

   static int q[MX],top;q[top=1]=x;register int i;

    for(i=x;nrt(i);i=fa[i]) q[++top]=fa[i];

    for(;top;--top) down(q[top]);

    for(;nrt(x);rotate(x)) if(nrt(fa[x])) rotate(get(x)^get(fa[x])?x:fa[x]);

    up(x);

}

inline void access(int x){register int i;for(i=0;x;x=fa[i=x])Splay(x),c[x][1]=i,up(x);}

inline void cut(int x){access(x);Splay(x);upd(c[x][0],-val[x]);fa[c[x][0]]=0;c[x][0]=0;up(x);}

inline void link(int x,int y){fa[x]=y;access(y);Splay(y);upd(y,val[x]);}

inline void add(int x,int y){access(x);Splay(x);siz[x]=(siz[x]+y)%mod;X[x]=(X[x]+1ll*(val[x]-1)*y%mod)%mod;}

inline int query(int x){access(x);Splay(x);return X[x];}

inline void Insert(int x)

{

    int p=last,np=++cnt;step[np]=step[p]+1;val[np]=1;

    for(;p&&!ss[p][x];p=fail[p]) ss[p][x]=np;

    if(!p)link(np,1),fail[np]=1,add(np,step[np]);

    else

    {

        int q=ss[p][x];

        if(step[q]==step[p]+1)link(np,q),fail[np]=q,add(np,step[np]-step[q]);

        else

        {

            int nq=++cnt;step[nq]=step[p]+1;

            memcpy(ss[nq],ss[q],sizeof ss[nq]);

            add(nq,step[nq]-step[fail[q]]);

            add(q,step[fail[q]]-step[nq]);

            add(np,step[np]-step[nq]);

            link(nq,fail[q]);cut(q);link(q,nq);link(np,nq);

            fail[nq]=fail[q];fail[q]=fail[np]=nq;

            for(;ss[p][x]==q;p=fail[p]) ss[p][x]=nq;

        }

    }

    last=np;

    tmp=(tmp+query(last))%mod;

    ans=(ans+tmp)%mod;

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

}

char s[MN];

int main()

{

	int i,Len=read();

	scanf("%s",s+1);

	for(i=1;i<=Len;++i) Insert(s[i]-'a');

}

T3 hunter

概率dp

\(f_{i,j}\)表示得是当前被射中的是第\(i\)号猎人，当前还有\(j\)个人时，的答案。

当然我们所说的\(i\)号是对当前剩余猎人进行排序后，从\(1\)号猎人开始数的第\(i\)个，所以\(i\leq j\)

有一个约定是当前剩下的人中一定有\(1\),不然答案就是\(0\)了，我们根本不需要计算

于是：

\[f_{i,j}=\frac{1}{2}(f_{Nex(i),j,},f_{nex(i),j-1})
\]

自行意会，这里的\(Nex(i)\)和\(nex(i)\)不是同一个，因为当人数减少后，对应编号会变。

我们设\(t_{i,j}=f_{nex(i),j-1}\)，注意\(t_{1,j}=0\)，要特别计算

但是，计算\(f_{i,j}\)，要求的值形成了若干个环

小学数学告诉我们：

环的数量是\(gcd(j,k)\)

环的长度是\(\frac{j}{gcd(j,k)}\)

我们对每个环进行计算，设这个环上的元素一次是\(a_{p_1},a_{p_2},...,a_{p_n}\)

于是就有

\[a_{p_i}=\frac{1}{2}(t_{P_i}+a_{p_i})
\]

暴力解方程可以得知：

\[a_1=\frac{2^{n-1}t_1+2^{n-2}t_2+...+t_n}{2^n-1}
\]

其他的就是轮换一下，就不说啦

然后，就没有然后了

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

const int mod=1e9+7,MN=2005;

int n,k;

int fpow(int x,int m){int r=1;for(;m;m>>=1,x=1ll*x*x%mod)if(m&1)r=1ll*r*x%mod;return r;}

int gcd(int x,int y){return x?gcd(y%x,x):y;}

int f[MN][MN],t[MN],p2[MN];

signed main()

{

	register int i,j,h,ln;

	n=read();k=read();

	f[1][1]=1;

	for(p2[0]=i=1;i<=n+1;++i) p2[i]=p2[i-1]*2ll%mod;

	for(i=2;i<=n;++i)

	{

		#define nx(x) ((x+k%i-1)%i+1)

		for(j=1;j<=i;++j)

		{

			int nex=((k-1)%(i-1)+1+j-1-1)%(i-1)+1;

			t[j]=f[nex][i-1];

		}

		t[1]=0;

		int num=gcd(i,k%i),len=i/num,val,Inv=fpow(p2[len]-1,mod-2);

		for(j=1;j<=num;++j)

		{

			val=0;

			for(ln=len,h=j;ln;--ln,h=nx(h)) (val+=1ll*p2[ln-1]*t[h]%mod)%=mod;

			f[j][i]=1ll*val*Inv%mod;

			for(ln=len,h=j;ln>1;--ln,h=nx(h))

			{

				(val+=mod-1ll*p2[len-1]*t[h]%mod)%=mod,val=2ll*val%mod,(val+=t[h])%=mod;

				f[nx(h)][i]=1ll*val*Inv%mod;

			}

		}

	}

	printf("%d\n",f[(k-1)%n+1][n]);

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

FCS省选模拟赛 Day3

Description

Solution

T1 game

T2 string

T3 hunter

最新文章

热门文章