C++14(g++5.4) 解法, 执行用时: 534ms, 内存消耗: 26820K, 提交时间: 2019-01-07 16:56:43

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MANY=3500000;
const int N=11;
struct zk { int k,p; }; zk part1[N],part2[N];
int n,m,half,ans,top1,top2;   int reach1[MANY],reach2[MANY];
void read()
{
    int i;
    scanf("%d%d",&n,&m);
    half=n/2;
    for (i=1;i<=half;i++)
        scanf("%d%d",&part1[i].k,&part1[i].p);
    for (i=1;i<=n-half;i++)
        scanf("%d%d",&part2[i].k,&part2[i].p);
    return;
}
int quick(int p,int q)
{
    int temp;
    if (q==1) return p;
    temp=quick(p,q/2);
    if (q%2==0)
        return temp*temp;
    else
        return temp*temp*p;
}
void dfs1(int step,int now)
{
    int i;
    if (step==half+1)
    {
        reach1[++top1]=now;
        return;
    }
    for (i=1;i<=m;i++)
        dfs1(step+1,now+quick(i,part1[step].p)*part1[step].k);
    return;
}
void dfs2(int step,int now)
{
    int i;
    if (step==n-half+1)
    {
        reach2[++top2]=now;
        return;
    }
    for (i=1;i<=m;i++)
        dfs2(step+1,now+quick(i,part2[step].p)*part2[step].k);
    return;
}
void work()
{
    int i=1,j=top2,last1,last2;
    sort(reach1+1,reach1+1+top1);
    sort(reach2+1,reach2+1+top2);
    for (i=1;i<=top1;i++)
    {
        while (reach1[i]+reach2[j]>0&&j>0) j--;
        if (j<=0) break;
        if (reach1[i]+reach2[j]!=0) continue;
        last1=1; last2=1;
        while (reach1[i+1]==reach1[i]&&i<top1) { i++; last1++; }
        while (reach2[j-1]==reach2[j]&&j>1)  { j--; last2++; }
        ans=ans+last1*last2;
    }
    printf("%d",ans);
    return;
}
int main()
{
    read();
    dfs1(1,0);
    dfs2(1,0);
    work();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 283ms, 内存消耗: 31172K, 提交时间: 2022-10-23 15:19:48

#include<bits/stdc++.h>
using namespace std;
int n,m,tp,k[123],p[1234],res[1234][56],ans=0,vis[4000000],h[4000000];
int qpow(int a,int b){return res[a][b];}
int fk(int x){
	static int y;
	y=1LL*abs(x)*233%3926081;
	while(h[y]&&h[y]!=x)++y;
	h[y]=x;return y;
}
void dfs1(int pos,int x){
	if(pos>tp){
		vis[fk(x)]++;
		return;
	}for(int i=1;i<=m;i++)dfs1(pos+1,k[pos]*qpow(i,p[pos])+x);
}
void dfs2(int pos,int x){
	if(pos>n){
		ans+=vis[fk(x)];
		return;
	}for(int i=1;i<=m;i++)dfs2(pos+1,x-k[pos]*qpow(i,p[pos]));
}
void init(){
	int nw,M;M=INT_MAX;
	for(int i=1;i<=m;i++){
		nw=i;
		for(int j=1;j<39;j++){
			res[i][j]=nw;
			if(1LL*nw*i>M) break;
			nw*=i;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>k[i]>>p[i];
	init();tp=n/2;
	if(n==1) vis[0]=1;
	else dfs1(1,0);
	dfs2(tp+1,0);
	cout<<ans;
}