题目
![P5691 [NOI2001] 方程的解数,算法,c++,深度优先,折半搜索,mitm](https://imgs.yssmx.com/Uploads/2023/07/617824-1.png)
![P5691 [NOI2001] 方程的解数,算法,c++,深度优先,折半搜索,mitm](https://imgs.yssmx.com/Uploads/2023/07/617824-2.png)
思路
暴搜显然会TLE，所以这时候就应该请出DFS的伙伴——折半搜索（meet in the middle）了
折半搜索的思路就是先搜完后一半后，借助这一半的数据来搜索前一半，效率是原来的2倍
这个题怎么才能折半搜索呢？
看这个方程![P5691 [NOI2001] 方程的解数,算法,c++,深度优先,折半搜索,mitm](https://imgs.yssmx.com/Uploads/2023/07/617824-3.png)
我们可以将其拆成两半：
设k为n/2![P5691 [NOI2001] 方程的解数,算法,c++,深度优先,折半搜索,mitm](https://imgs.yssmx.com/Uploads/2023/07/617824-4.png)
这样就可以进行折半搜索了
注：在搜后一半的时候需要存的是负的值文章来源：https://www.toymoban.com/news/detail-617824.html
代码
#include<bits/stdc++.h>
using namespace std;
const int N=45;
int n,m,k[N],p[N];
int b[1<<23],tot;
long long ans;
void dfs_r(int i,int sum){
if(i==n) { b[++tot]=-sum;return; }
for(int x=1;x<=m;x++){
int t=k[i];
for(int j=1;j<=p[i];j++) t*=x;
dfs_r(i+1,sum+t);
}
}
void dfs_l(int i,int sum){
if(i==n/2) { int x=sum;ans+=upper_bound(b+1,b+1+tot,x)-lower_bound(b+1,b+1+tot,x);return; }//有多少个相同的解
for(int x=1;x<=m;x++){
int t=k[i];
for(int j=1;j<=p[i];j++) t*=x;
dfs_l(i+1,sum+t);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>k[i]>>p[i];
dfs_r(n/2,0);
sort(b+1,b+1+tot);
dfs_l(0,0);
cout<<ans<<endl;
return 0;
}
end
完结撒花文章来源地址https://www.toymoban.com/news/detail-617824.html
到了这里，关于P5691 [NOI2001] 方程的解数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
