折半思想和倍增思想不是同一种思想，但思想接近，并且都是优化程序的黑科技。
折半
即传说中的 (Meet) (in) (the) (middle) , 核心思想就是将原问题分成两个或多个部分，分别解决各个部分后合并。
适用范围 这种思想一般被广泛运用于优雅的暴力，比如暴搜。当然还可以和乘法逆元之类的东西合用.
（形如 (a*b*c*dequiv k(mod) (m)) 的式子可化为(a*bequiv k*(c*d)^{-1}(mod) (m)).）
操作步骤 将一组数据分为两组，分别搜索或暴力求得答案，然后合并答案。合并时通常需要使用排序+双指针，排序+二分等算法统计答案。有时并不是平均分配，可以考虑分为较小部分与较大部分，较小部分先暴搜排序，然后较大部分暴搜+二分即可剪枝。或直接分为两个较小部分与一个极小部分，极小部分直接分类讨论。
倍增
即传说中可以直接求答案也可以用来优化 (dp) 的神器，核心思想就是递归计算，对于一个规模为 (n) 的问题，求出如适用范围的通式。
适用范围
[f(x)=left{egin{aligned}g(f(x-1))\g(f(frac x 2))end{aligned}
ight.
]
其中 (g(x)) 为可推递推式。
操作步骤 求递推式。若优化 (dp) 先思考是否可以直接倍增求得 (f(x))，再推 (dp) 方程。
//bzoj 2165
#include<bits/stdc++.h>
#define ll long long
using 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<<p;
}
int main()
{
T=read();
while (T--)
{
n=read(); m=read();
memset(f,0xef,sizeof(f));
memset(g,0xef,sizeof(g));
for(int i=1;i<=n;i++)g[i][i]=0;
ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[0][i][j]=read();
if(!f[0][i][j])f[0][i][j]=-1e18;
}
work1();
while(p--)work2();
printf("%lld
",ans+1);
}
return 0;
}