记录编号	595684	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]方程的解数	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	3.653 s
提交时间	2024-10-15 20:42:24	内存使用	9.93 MiB

#include<bits/stdc++.h>
using namespace std ;
long long n,m,x[15],y[15],a[10000005],pp,tp,as;
long long pw(long long xx,long long yy){
    long long s=1;
    while(yy){
        if(yy%2==1){
            s*=xx;
        }
        xx*=xx;
        yy/=2;
    }
    return s;
}
void dfs1(long long p,long long s){
	if(p==n/2+1){
		a[++tp]=s;
		return;
	}
	for(int i=1;i<=m;i++){
		dfs1(p+1,s+x[p]*pw(i,y[p]));
	}
	return;
}
void dfs2(long long p,long long s){
	if(p>n){
	    long long pp;
		pp=upper_bound(a+1,a+tp+1,-s)-lower_bound(a+1,a+tp+1,-s);
		as+=pp;
		return;
	}
	for(int i=1;i<=m;i++){
	    dfs2(p+1,s+x[p]*pw(i,y[p]));
	}
}
int main(){
    freopen("equation1.in","r",stdin);
    freopen("equation1.out","w",stdout);
    cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>x[i]>>y[i];
    }
	dfs1(1,0);
	sort(a+1,a+tp+1);
	dfs2(n/2+1,0);
	cout<<as;
	return 0 ;
}