首页 > 其他 > 详细

bzoj4569-[Scoi2016]萌萌哒

时间:2019-01-14 13:33:56      阅读:142      评论:0      收藏:0      [点我收藏+]

Description

一个长度为n的大数,用S1S2S3...Sn表示,其中Si表示数的第i位,S1是数的最高位,告诉你一些限制条件,每个条
件表示为四个数,l1,r1,l2,r2,即两个长度相同的区间,表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...S
r2完全相同。比如n=6时,某限制条件l1=1,r1=3,l2=4,r2=6,那么123123,351351均满足条件,但是12012,13
1141不满足条件,前者数的长度不为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

Solution

发现约束条件等价于若干组 \(S_{l_{i1} + d} = S_{l_{i2} + d}\).
这样, 记录相等的组数\(cnt\), 那么
\[ Ans = 9*10^{cnt-1}\]

这样就可以用并查集维护, 时间复杂度 \(O(m*n*\alpha (n))\).

考虑每次都是一段连续的区间, 利用倍增优化:
fa[l][p]表示起点为p, 长度为l的区间的父亲,修改时分段修改;
最后查询时, 从\(l\) 合并到\(l-1\), 一直到0, fa[0][p]=p的就是它所在组的根, 计数即可.
时间复杂度 \(O(m*\log n*\alpha (n))\).

Code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;

//---------------------------------------
const int nsz=1e5+50,lnsz=25;
const ll nmod=1e9+7;
int n,m,ln,cnt;
int fa[lnsz][nsz];
void inituf(){rep(i,0,ln)rep(j,1,n)fa[i][j]=j;}
int getfa(int a,int l){return fa[l][a]==a?a:fa[l][a]=getfa(fa[l][a],l);}
void merge(int a,int b,int l){
    a=getfa(a,l),b=getfa(b,l);
    if(a!=b)fa[l][a]=b;
}
void p(){
    repdo(i,ln,0){
        printf("l=%d ",i);
        rep(j,1,n)printf("%d ",getfa(j,i));
        printf("\n");
    }
}
ll qp(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%nmod;
        b>>=1,a=a*a%nmod;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    ln=22;
    int a,b,c,d;
    inituf();
    rep(i,1,m){
        cin>>a>>b>>c>>d;
        repdo(j,ln,0){
            if(a+(1<<j)-1<=b)merge(a,c,j),a+=(1<<j),c+=(1<<j);
        }
//      p();
    }
    repdo(i,ln,1){
        repdo(j,n-(1<<i)+1,1){
            merge(j,getfa(j,i),i-1);
            merge(j+(1<<(i-1)),getfa(j,i)+(1<<(i-1)),i-1);
        }
    }
    rep(i,1,n)if(getfa(i,0)==i)++cnt;
    cout<<9ll*qp(10,cnt-1)%nmod<<'\n';
    return 0;
}

bzoj4569-[Scoi2016]萌萌哒

原文:https://www.cnblogs.com/ubospica/p/10266044.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!