NOI2001 方程的解数（双向搜索）

solution

一道非常经典的双向搜索题目，先将前3个未知数枚举一遍得到方程的前半部分所有可能的值，取负存入第一个队列中再将后3个未知数枚举一遍，存入第二个队列中。这样我们只要匹配两个队列中相同的元素即可使方程为零。方法：将两个队列排序，用尺取法+乘法原理扫一遍即可。

=>

code：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int

using namespace std;

int ans;
int n,m,l,t1,t2;
int k[7],p[7];
int a[3500001];
int b[3500001];

inline int qr(){
	char ch;int sign=1;
	while((ch=getchar())<'0'||ch>'9')
		if(ch=='-')sign=-1;
	int res=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
		res=res*10+(ch^48);
	return res*sign;
}

inline int fast(int x,int y){
	int res=1;
	while(y){
		if(y&1)res*=x;
		x*=x; y>>=1;
	}return res;
}

inline void dfs(int t,int tot){
	if(t>l){a[++t1]=-tot;return ;}
	for(rg i=1;i<=m;++i)
		dfs(t+1,tot+k[t]*fast(i,p[t]));
}

inline void dfs2(int t,int tot){
	if(t>n){b[++t2]=tot;return ;}
	for(rg i=1;i<=m;++i)
		dfs2(t+1,tot+k[t]*fast(i,p[t]));
}

int main(){
	//freopen("equation.in","r",stdin);
	//freopen("equation.out","w",stdout);
	n=qr(),m=qr();l=n/2;
	for(rg i=1;i<=n;++i)
		k[i]=qr(),p[i]=qr();
	dfs(1,0); dfs2(l+1,0);
	sort(a+1,a+t1+1);
	sort(b+1,b+t2+1);
	for(rg i=1,j=1,su,x,y;i<=t1;++i){
		if(a[i]<b[j])continue;
		while(b[j]<a[i]&&j<=t2)++j;
		if(j>t2)break;
	    if(a[i]==b[j]){
			su=a[i]; x=y=0;
			while(a[i]==su&&i<=t1)++i,++x;
			while(b[j]==su&&j<=t2)++j,++y;
			ans+=x*y;--i;
		}
	}
	printf("%d
",ans);
	return 0;
}