折半思想和倍增思想不是同一种思想，但思想接近，并且都是优化程序的黑科技。

折半

　　即传说中的 \(Meet\) \(in\) \(the\) \(middle\) , 核心思想就是将原问题分成两个或多个部分，分别解决各个部分后合并。

　　适用范围 这种思想一般被广泛运用于优雅的暴力，比如暴搜。当然还可以和乘法逆元之类的东西合用.

　　（形如 \(a*b*c*d\equiv k(mod\) \(m)\) 的式子可化为\(a*b\equiv k*(c*d)^{-1}(mod\) \(m)\).）

　　操作步骤 将一组数据分为两组，分别搜索或暴力求得答案，然后合并答案。合并时通常需要使用排序+双指针，排序+二分等算法统计答案。有时并不是平均分配，可以考虑分为较小部分与较大部分，较小部分先暴搜排序，然后较大部分暴搜+二分即可剪枝。或直接分为两个较小部分与一个极小部分，极小部分直接分类讨论。

倍增

　　即传说中可以直接求答案也可以用来优化 \(dp\) 的神器，核心思想就是递归计算，对于一个规模为 \(n\) 的问题，求出如适用范围的通式。

　　适用范围

\[f(x)=\left\{\begin{aligned}g(f(x-1))\\g(f(\frac x 2))\end{aligned}\right.\]

　　其中 \(g(x)\) 为可推递推式。

　　操作步骤 求递推式。若优化 \(dp\) 先思考是否可以直接倍增求得 \(f(x)\)，再推 \(dp\) 方程。

//bzoj 2165#include
    
     #define ll long longusing namespace std;int T,n,p;bool flag;ll f[70][105][105],g[105][105],t[105][105],ans,m;    //f[i][j][k] 记录从第i个房间走2^p步到达j房间最多能走几层                                                      //g[i][j] 记录从i房间走到j房间最多能走几层 inline ll read(){    ll a=0,f=1; char c=getchar();    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}    return a*f;}inline void work1(){    for(p=1;p<=log2(m);p++)    for(int k=1;k<=n;k++)    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++){        f[p][i][j]=max(f[p-1][i][k]+f[p-1][k][j],f[p][i][j]);        if(i==1&&f[p][i][j]>=m)return;              //已经从第一层走到了M以上     }}inline void work2(){    memset(t,0xef,sizeof(t));    for(int k=1;k<=n;k++)    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++){        t[i][j]=max(t[i][j],f[p][i][k]+g[k][j]);    //为了避免走第2^p步刚好跨越了M，所以只需要求出最接近M且小于M的值，再在最后ans++跨越M即可          if(i==1&&t[i][j]>=m)return;    }    memcpy(g,t,sizeof(g));                          //迭代     ans+=1ll<