题解 P3295 【[SCOI2016]萌萌哒】

· · 题解

关于各种神奇的倍增法

倍增

其实倍增法不仅局限于快速幂，后缀数组，ST表，求lca之类的特定算法，而是用来解决一类特定问题的。

倍增原理

看似玄学的倍增其实源于两个数学等式

1.2^n=2^(n-1)+2^(n-1)

2.N=sigma(pi*2^i) [i∈(0,+∞)] {中pi为N的二进制第i位}

想必任何一个知道二进制的人都明白上述两个等式吧……

而倍增法的唯一要求的是，被称之为“+”的运算满足结合律(有些人也成操作满足可合并性)

具体来讲，倍增法用到的地方一般是，我们现在要询问/修改一些东西，然后我们发现操作具有合并性，之后呢，我们对于每个大小为2^i的东西预处理出来一个答案，等到询问的时候，就将询问的东西大小用二进制表达，将预处理出来的每个东西合并起来就得到了答案

常用的两类二进制拆分代码

for(int i=0;p;p>>=1,i++){/*do sth*/}
for(int i=20;p>0;i--){if(p>po[i]){p-=po[i]}/*do sth*/}

其中上面一个适用于p已知的情况(比如倍增求lca，跳到深度相等的那段代码)

下面的一个适用于p未知，但是可以比较p和某个值的大小，以及可以做相减运算 (比如lca第二段，两个点一起向上跳，但是不知道lca的深度的情况，但是我们用这个代码在未知lca深度的情况下对lca深度做了二进制拆分)

然后我们来结合这道题讲一下如何魔改倍增法，因为这个玩意和dp，分治法都很像，都是根据某一个问题的性质设计了类似的"方法"，根本不是有板子的算法，所以我们要具体问题具体分析……

本题题解

首先我们发现题目中给了我们一些区间相等的关系，之后我们发现，如果从子串的思路想会进入死胡同，因为串都没给你哪里来的后缀数据结构？

发现这道题本质上是个计数问题，我们考虑枚举每个点可以取的值，发现有些其他点必须和他取值一样，否则不满足题意区间相等的要求，(这里其实做了一步转化，区间相等<-->对应点相等)

那么我们就有办法维护这个相等关系了,直接并查集维护复杂度O(n^2)，30pts get√，最后的答案为9*10^(num-1) num为并查集个数，因为最高位是不可以取零的

然后发现是传统暴力的复杂度不均衡问题，我们的处理询问，是O(N^2)的但是，我们的查找，仅仅是O(N)的……所以我们要平衡这个扭曲的复杂度，使得询问查找都变成O(NlogN)

那么怎么办呢，并查集的并操作具有可合并性，所以我们可以考虑上倍增。

我们可以将一个点拆成logN个点，分别代表从点i开始，长度为2^k的子串 那么当我们处理两个区间相等的关系时，对区间做二进制拆分，拆成log个区间，分别并起来即可

当然我们这样做修改是省心了，但是同时查询的时候也会带来一些麻烦……因为，我们要求的信息是最底层的，只能是长度为1的区间，而不能有奇奇怪怪的区间 不过没关系，我们这时运用等式1，拆分并查集

具体来讲，我们从最长的区间开始逐个枚举，每次查找他和他的父亲，然后把它和父亲都劈成两半，前一半和前一半连边，后一半和后一半连边即可，这样相当于把较长区间并查集拆成两个一半的并查集

最后我们就有了一些关于那些点相等的信息，直接计算并查集个数即可

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=(a*a)%mod){if(p&1)r=(r*a)%mod;}return r;}
const int N=100010;int n;int tr[20][N];int log[N];int ctt;//用来给各个区间编号
inline void createlog()//这里打表log其实并没咋用……
{int i=1;for(int j=2;j<=n;j++){if(j==(1<<(i+1)))i++;log[j]=i;}}
struct bcj//只写了路径压缩，理论来讲是log^2N的，但是路径压缩的均摊复杂度常数小于1……
{
    int fa[20*N];
    inline void ih(){for(int i=1;i<=ctt;i++)fa[i]=i;}
    inline int f(int x){return fa[x]=(fa[x]==x)?x:f(fa[x]);}
    inline void u(int x,int y){fa[f(x)]=f(y);}
}s;int m;int siz;bool book[N];
inline void dtr(int v,int& y){v%=n;y=v?v:n;}//解编号函数
int main()
{
    scanf("%d%d",&n,&m);createlog();
    for(int i=0;i<=log[n];i++)
    {for(int j=1;j<=n;j++){tr[i][j]=++ctt;}}//分配编号
    s.ih();
    for(int i=1;i<=m;i++)
    {
        int l;int r;int len;int d;
        scanf("%d%d%d%d",&l,&r,&len,&d);
        d=len-l;len=r-l+1;//len区间长度,d偏移量
        for(int k=0;len;len>>=1,k++)//这里的二进制拆分可能用了些位运算的奇技淫巧~
        {
            if(len&1)
            {
                int p1=l+((len>>1)<<(k+1));int p2=p1+d;
                s.u(tr[k][p1],tr[k][p2]);//把对应区间并起来
            }
        }
    }
    for(int i=log[n];i>=1;i--)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)//分裂并查集
        {
            int fa=s.f(tr[i][j]);if(fa==tr[i][j]){continue;}int y;dtr(fa,y);//前一半后一半连边
            s.u(tr[i-1][j],tr[i-1][y]);s.u(tr[i-1][j+(1<<(i-1))],tr[i-1][y+(1<<(i-1))]);
        }
    }
    for(int i=1;i<=n;i++)//计算并查集个数
    {
        int fa=s.f(tr[0][i]);int y;dtr(fa,y);
        if(!book[y]){book[y]=true;siz++;}
    }
    printf("%lld",(9*po(10,siz-1))%mod);return 0;//拜拜程序~
}