xsy 2412【BZOJ4569】【Scoi2016】萌萌哒

Description

 

Description

    一个长度为n的大数,用S1S2S3...Sn表示,其中Si表示数的第i位,S1是数的最高位,告诉你一些限制条件,每个条件表示为四个数,l1,r1,l2,r2,即两个长度相同的区间,表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...Sr2完全相同。比如n=6时,某限制条件l1=1,r1=3,l2=4,r2=6,那么123123,351351均满足条件,但是12012,131141不满足条件,前者数的长度不为6,后者第二位与第五位不同。问满足以上所有条件的数有多少个。

Input

    第一行两个数n和m,分别表示大数的长度,以及限制条件的个数。接下来m行,对于第i行,有4个数li1,ri1,li2,ri2,分别表示该限制条件对应的两个区间。

    1≤n≤10^5,1≤m≤10^5,1≤li1,ri1,li2,ri2≤n;并且保证ri1-li1=ri2-li2。

Output

    一个数,表示满足所有条件且长度为n的大数的个数,答案可能很大,因此输出答案模10^9+7的结果即可。

Sample Input

4 2
1 2 3 4
3 3 3 3

Sample Output

90

题解思路 先设一个数组f[i][j],表示从i个数开始向后2的j次方个数与从f[i][j]个数开始向后2的j次方个数相同。
对于每两个相等的区间,我们先用倍增将它们划分为多个长度2的次方个小段,再将每一个小段以并查集的方式合并。 这个操作的时间复杂度是O(nlogn)。 然后从2的最大次方开始,若f[i][j]=k,则将其转换为合并f[i][j-1],k以及f[i+2^(j-1)][j],k。 这个操作的时间复杂度也是O(nlogn)的。 最后统计一个s,表示f[i][0]=i的i的个数。 最后用快速幂求出9*(10^(s-1))即可(开头不能为0)(其实龟速乘也可以) 这个的时间复杂度是O(n)的。 所以总的时间复杂度是O(nlogn)
 
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,l1,l2,r1,r2,f[100001][21],v[21],cnt=-1,fx,fy,s,ans=1,mod=1000000007;
long long fa(long long id,long long a){
    if(f[a][id]!=a)f[a][id]=fa(id,f[a][id]);
    return f[a][id];
}
long long find(long long a){
    s=10ll;
    while(a>0){
        if(a%2ll)ans=(ans*s)%mod;
        s=(s*s)%mod;
        a=a/2ll;
    }
}
void merge(long long id,long long x,long long y){
    fx=fa(id,x);
    fy=fa(id,y);
    if(fx!=fy)f[fx][id]=fy;
}
int main(){
    v[0]=1;
    for(long long i=1;i<=20;i++)v[i]=v[i-1]*2;
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++)for(long long j=0;j<=20;j++)f[i][j]=i;
    for(long long i=1;i<=m;i++){
        scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
        for(long long j=20;j>=0;j--){
            if(v[j]<=r1-l1+1){
                merge(j,l1,l2);
                l1=l1+v[j];
                l2=l2+v[j];
            }
        }
    }
    for(long long i=20;i;i--){
        for(long long x=1;x+v[i]-1<=n;x++){
            s=fa(i,x);
            merge(i-1,x,s);
            merge(i-1,x+v[i-1],s+v[i-1]);
        }
    }
    for(long long i=1;i<=n;i++){
        s=fa(0,i);
        if(s==i)cnt++;
    }
    find(cnt);
    ans=ans*9ll;
    ans=ans%mod;
    printf("%lld\n",ans);
}

  

 
上一篇:洛谷P1196 [NOI2002] 银河英雄传说


下一篇:文艺平衡树算法