倍增&矩阵乘法 专题复习

倍增&矩阵乘法 专题复习

PreWords

这两个基础算法我就不多说啦，但是还是要介绍一下" 广义矩阵 "乘法

其实就是把矩阵换成取\(max\)，然后都一样。。。

据神仙LBC说：这不显然是对的吗！

\[\
\]

\[\
\]

[usaco2007 Nov] relays 奶牛接力跑

离散一下，然后套矩阵乘法\(a[i][j]\)记录从\(i\)出发到\(j\)的最小答案，快速幂即可

const int N=410,P=1e4+7;

int n,m,s,t;
int a[N],b[N],c[N];
int h[N],cnt;

inline void chk(ll &a,ll b) { ((a>b)&&(a=b)); }

struct Mat{
    ll a[N][N];
    void init(){ memset(a,63,sizeof a); }
    Mat operator * (const Mat x) const {
        Mat res; res.init();
        rep(i,1,cnt) rep(j,1,cnt) rep(k,1,cnt) chk(res.a[i][k],a[i][j]+x.a[j][k]);
        return res;
    }
} res,x;

int main() {
    n=rd(),m=rd(),s=rd(),t=rd();
    rep(i,1,m) {
        c[i]=rd(),a[i]=rd(),b[i]=rd();
        h[++cnt]=a[i];
        h[++cnt]=b[i];
    }
    sort(h+1,h+cnt+1);
    cnt=unique(h+1,h+cnt+1)-h-1;
    x.init();
    rep(i,1,m) {
        a[i]=lower_bound(h+1,h+cnt+1,a[i])-h;
        b[i]=lower_bound(h+1,h+cnt+1,b[i])-h;
        chk(x.a[a[i]][b[i]],c[i]);
        chk(x.a[b[i]][a[i]],c[i]);
    }
    s=lower_bound(h+1,h+cnt+1,s)-h;
    t=lower_bound(h+1,h+cnt+1,t)-h;
    n--;
    res=x;
    while(n) {
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    printf("%lld\n",res.a[s][t]);
}

\[\
\]

\[\
\]

[BZOJ4773] 负环

基本类似，但是由于这题要二分答案，直接套是\(log^2\)，用倍增替换二分即可

int n,m;

inline void chk(int &a,int b) { ((a>b)&&(a=b)); }

struct Mat{
    int a[N][N];
    void init(){
        memset(a,63,sizeof a);
    }
    Mat operator * (const Mat x) const {
        Mat res; res.init();
        rep(i,1,n) rep(j,1,n) rep(k,1,n) chk(res.a[i][k],a[i][j]+x.a[j][k]);
        return res;
    }
}st,Pow[10];

int main() {
    n=rd(),m=rd();
    st.init();
    rep(i,1,n) st.a[i][i]=0;
    rep(i,1,m) {
        int a=rd(),b=rd(),c=rd();
        chk(st.a[a][b],c);
    }
    Pow[0]=st;
    rep(i,1,9) Pow[i]=Pow[i-1]*Pow[i-1];
    int fl=0;
    rep(i,1,n) if(Pow[9].a[i][i]<0) fl=1;
    if(!fl) return puts("0"),0;
    Mat now=st;
    int res=2;
    drep(i,9,0) {
        Mat t=now*Pow[i];
        fl=0;
        rep(j,1,n) if(t.a[j][j]<0) fl=1;
        if(!fl) now=t,res+=1<<i;
    }
    printf("%d\n",res);
}

\[\
\]

\[\
\]

[BZOJ4417] [Shoi2013]超级跳马

有奇偶性问题？开两倍的数组记录当前这一列是奇数还是偶数即可

最后注意由于要保证跳了\(m\)格，还要减去跳了\(m-1\)格以内的答案

const int N=110,P=30011;

int n,m;

struct Mat {
    int a[N][N];
    void init(){ memset(a,0,sizeof a); }
    Mat operator * (const Mat x) const {
        Mat res; res.init();
        rep(i,1,n*2) rep(j,1,n*2) rep(k,1,n*2) res.a[i][k]=(res.a[i][k]+a[i][j]*x.a[j][k])%P;
        return res;
    }
}res,res2,x,st;

int main() {
    n=rd(),m=rd();
    rep(i,1,n) {
        if(i>1) x.a[i][i-1]++;
        if(i<n) x.a[i][i+1]++;
        x.a[i][i]++;
        x.a[i][i+n]++;
        x.a[i+n][i]++;
    }
    m--;
    st=x;
    res=x;m--;
    int t=m;
    for(;m;m>>=1,x=x*x) if(m&1) res=res*x;
    m=t;
    if(m>0) {
        x=st;
        res2=x;m--;
        for(;m;m>>=1,x=x*x) if(m&1) res2=res2*x;
    }
    int ans=(res.a[1][n]+res.a[1][n*2]-res2.a[1][n]-res2.a[1][n*2])%P;
    ans=(ans%P+P)%P;
    printf("%d\n",ans);
}

\[\
\]

\[\
\]

[BZOJ2093] [Poi2010]Frog

这个题是一个标准的倍增吧。。。

关于预处理第k远

尺取两边 \(i\) 第一个 \(j\) 满足 距离在 \(abs(a[j]-a[i])\) 以内的点个数 $ \ge k$，当然也可以二分

然后比较两个谁近

尺取过程可以参考代码

以下是二分

 rep(i,1,n) {
        reg int l=max(1,i-k),r=min((int)i,n-k),res1=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(a[mid+k]<=a[i]+(a[i]-a[mid])) l=mid+1,res1=mid;
            else r=mid-1;
        }
        l=max(k+1,(int)i),r=min(i+k,n);
        reg int res2=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(a[mid-k]>=a[i]-(a[mid]-a[i])) r=mid-1,res2=mid;
            else l=mid+1;
        }
        if(res1==-1 || (res2!=-1 && a[res2]-a[i]<a[i]-a[res1])) Nxt[i][0]=res2;
        else Nxt[i][0]=res1;
    }
}

以下是尺取

const int N=1e6+10;

int n,k;
ll m;
ll a[N];
int Nxt[2][N];
int ans[N];
int res1[N],res2[N];

int main() {
    n=rd(),k=rd(); m=rd();
    rep(i,1,n) a[i]=rd();
    int p=1;
    rep(i,1,n) {
        if(a[k+1]>a[i]+a[i]-a[1]) res1[i]=-1;
        else {
            while(p<n-k && p<i-1 && a[p+k+1]<=a[i]+a[i]-a[p+1]) p++;
            res1[i]=p;
        }
    }
    p=n;
    drep(i,n,1) {
        if(a[n-k]<a[i]+a[i]-a[n]) res2[i]=-1;
        else {
            while(p>k+1 && p>i+1 && a[p-k-1]>=a[i]+a[i]-a[p-1]) p--;
            res2[i]=p;
        }
    }
    rep(i,1,n) {
        if(res1[i]==-1 || (res2[i]!=-1 && a[res2[i]]-a[i]<a[i]-a[res1[i]])) Nxt[0][i]=res2[i];
        else Nxt[0][i]=res1[i];
    }
    rep(i,1,n) ans[i]=i;
    int cur=1;
    for(reg int i=0;(1ll<<i)<=m;++i) {
        cur^=1;
        if(i) for(reg int j=1;j<=n;++j) Nxt[cur][j]=Nxt[!cur][Nxt[!cur][j]];
        if(m&(1ll<<i)) for(reg int j=1;j<=n;++j) ans[j]=Nxt[cur][ans[j]];
    }
    rep(i,1,n) printf("%d ",ans[i]);
}

\[\
\]

\[\
\]

[BZOJ4082] [Wf2014]Surveillance

仿佛是一个比较经典的问题？

断环成链

\(nxt[i][j]\)记录当前从\(i\)开始，覆盖\(2^j\)个区间的能覆盖的最远位置

每一个点开始倍增到第一个能跨越长度\(n\)的位置，复杂度\(O(n \ log \ n)\)

但事实上可以带权并查集维护，\(O(n \ \alpha(n) )\)

倍增

const int N=2e6+10;

int n,m;
struct Node {
    int l,r;
    bool operator < (const Node __) const {
        return l<__.l;
    }
} Seg[N];
int fa[21][N];
int cnt;

int main() {
    n=rd(),m=rd();
    rep(i,1,m) {
        int l=rd(),r=rd();
        if(l<=r) {
            Seg[++cnt]=(Node){l,r};
            Seg[++cnt]=(Node){l+n,r+n};
        } else Seg[++cnt]=(Node){l,r+n};
    }
    sort(Seg+1,Seg+cnt+1);
    int p=1,ma=0;
    rep(i,1,n*2+1) {
        while(p<=cnt && Seg[p].l<=i) {
            ma=max(ma,Seg[p++].r);
        }
        fa[0][i]=max(ma+1,(int)i);
    }
    rep(i,1,20) rep(j,1,n*2+1) fa[i][j]=fa[i-1][fa[i-1][j]];
    int ans=1e9;
    rep(i,1,n) {
        int p=i,res=0;
        drep(j,20,0) if(fa[j][p]<i+n) p=fa[j][p],res+=1<<j;
        if(fa[0][p]>=i+n) ans=min(ans,res+1);
    }
    if(ans<1e8) printf("%d\n",ans);
    else puts("impossible");
}

并查集

const int N=2e6+10;

int n,m;
int ma[N],fa[N],dis[N];
int Find(int x) {
    if(x==fa[x]) return x;
    int f=fa[x];
    fa[x]=Find(fa[x]),dis[x]+=dis[f];
    return fa[x];
}

int main() {
    n=rd(),m=rd();
    rep(i,1,m) {
        int l=rd(),r=rd();
        chk(ma[l],((l<=r)?r:r+n));
    }
    reg int ans=1e9,ma=0;
    for(reg int i=1;i<=n*2+1;++i) fa[i]=i;
    for(reg int i=1;i<=n*2;++i) {
        chk(ma,::ma[i]);
        if(i>n) {
            int t=i-n;
            if(Find(t)>=i) chkmin(ans,dis[t]);
        }
        if(ma>=i) fa[i]=ma+1,dis[i]=1; //并查集维护最远覆盖
    }
    if(ans<=n) printf("%d\n",ans);
    else puts("impossible");
}

\[\
\]

\[\
\]

[BZOJ2085] [Poi2010]Hamsters

我并不会写，只能提供一组Hack数据

Input:

3 4

ab

cd

abcde

Output:

7

(abcdeab)

希望我没有读错题

\[\
\]

\[\
\]

[BZOJ4569][Scoi2016]萌萌哒

好题！

倍增维护并查集合并

一个倍增数组\(fa[i][j]\)维护从\(i\)开始长度为\(2^j\)的这一段与那一段长度相同的并在一起

将两端区间\(l1,r2,l2,r2\)用倍增剖开，在那一层的倍增数组上用并查集合并

最后每次将\(fa[i][j]\)向\(fa[i][j-1],fa[i+(1<<(j-1))][j-1]\)递推即可

int n,m;
struct UFS{
    int fa[N];
    int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); }
    void init(){ rep(i,1,n) fa[i]=i; }
    void merge(int x,int y) {
        fa[Find(x)]=Find(y);
    }
} B[18];
int LOG;
int main(){
    n=rd(),m=rd();
    for(LOG=0;(1<<LOG)<=n;LOG++) B[LOG].init();
    LOG--;
    rep(i,1,m) {
        int l1=rd(),r1=rd();
        int l2=rd();rd();
        if(l1==l2) continue;
        int len=r1-l1+1;
        drep(j,LOG,0) {
            if(len>=(1<<j)) {
                B[j].merge(l1,l2);
                l1+=1<<j,l2+=1<<j;
                len-=1<<j;
            }
        }
    }
    drep(i,LOG,1) {
        int len=(1<<(i-1));
        rep(j,1,n) {
            int f=B[i].Find(j);
            B[i-1].merge(j,f);
            B[i-1].merge(j+len,f+len);
        }
    }
    int cnt=0;
    rep(i,1,n) if(B[0].Find(i)==i) cnt++;
    ll ans=1;
    rep(i,1,cnt-1) ans=ans*10%P;
    ans=ans*9%P;
    printf("%lld\n",ans);
}