luogu P3295 [SCOI2016]萌萌哒

传送门

题目条件"两个子串\(S[l_1,r_1],S[l_2,r_2]\)完全相同"等价于\(\forall i \in[0,r_1-l_1+1],S_{l1+i}=S_{l_2+i}\),然后所有相同位置的都要选一种数字,把所有相同的放在一个集合,然后记集合个数为\(cn\)那么答案就是\(9*10^{cn-1}\),因为第一位不为0,然后就可以暴力并查集做到\(O(n^2)\)了

发现这样的连边是一个区间对应向另一个区间连边,可以考虑优化.因为连边要一一对应,所以可以ST表优化连边.就是每个点拆出\(log\)个点,代表以这个点为左端点的长度为\(2^k\)的区间,然后每次两个区间二进制拆分一下,在对应的点连边就好了个鬼.不过这样还是不对的,最后还要把这些连的边的作用发挥出来,就从上往下遍历ST表的每一层,某个点如果在当前层的根不是自己,那么就把自己的左儿子,右儿子分别向根的两个儿子连边,然后做下去

#include<bits/stdc++.h>

#define LL long long

#define db long double

#define il inline

#define re register

using namespace std;

const int N=1e5+10,mod=1e9+7;

il LL rd()

{

    LL x=0,w=1;char ch=0;

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

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

    return x*w;

}

int n,m,lz,ff[N][17],l2[N];

int findf(int x,int i){return ff[x][i]==x?x:ff[x][i]=findf(ff[x][i],i);}

int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}return an;}

int main()

{

    n=rd(),m=rd();

    lz=log2(n);

    for(int j=0;j<=lz;++j) l2[1<<j]=j;

    for(int j=0;j<=lz;++j)

        for(int i=1;i+(1<<j)-1<=n;++i)

            ff[i][j]=i;

    while(m--)

    {

        int l=rd(),r=rd(),ll=rd(),rr=rd();

        if(l==ll) continue;

        rr=rr-ll+1;

        while(rr)

        {

            int x=rr&(-rr),y=l2[x];

            ff[findf(l,y)][y]=findf(ll,y);

            l+=x,ll+=x;

            rr-=x;

        }

    }

    for(int j=lz;j;--j)

    {

        for(int i=1;i+(1<<j)-1<=n;++i)

            if(i!=findf(i,j))

                ff[findf(i,j-1)][j-1]=findf(findf(i,j),j-1),ff[findf(i+(1<<(j-1)),j-1)][j-1]=findf(findf(i,j)+(1<<(j-1)),j-1);

    }

    int cn=0;

    for(int i=1;i<=n;++i) cn+=i==findf(i,0);

    printf("%lld\n",9ll*fpow(10,cn-1)%mod);

    return 0;

}

巴特西

luogu P3295 [SCOI2016]萌萌哒

最新文章

热门文章