题意
题目链接
Sol
把前一半放在左边，后一半放在右边
meet in the middle一波
统计答案的时候开始想的是hash，然而MLE了两个点
实际上只要排序之后双指针扫一遍就行了
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int MAXN = 7, MAX = 1e7 10;
int K[MAXN], P[MAXN], N, M, ans;
int a1[MAX], c1, a2[MAX], c2, cnt[MAX];
int fp(int a, int p) {
int base = 1;
while(p) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
void dfs(int x, int Lim, int opt, int sum) {
if(x == Lim 1) {
if(!opt) a1[ c1] = sum;
else a2[ c2] = -sum;
return ;
}
for(int i = 1; i <= M; i ) dfs(x 1, Lim, opt, sum K[x] * fp(i, P[x]));
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= N; i ) cin >> K[i] >> P[i];
if(N <= 2) {
a1[ c1] = 0;
dfs(1, N, 1, 0);
} else {
dfs(1, N / 2, 0, 0);
dfs(N / 2 1, N, 1, 0);
}
sort(a1 1, a1 c1 1);
sort(a2 1, a2 c2 1);
int j = 1;
for(int i = 1; i <= c2; i ) {
if(i != 1 && (a2[i] == a2[i - 1])) {cnt[i] = cnt[i - 1]; continue;}
while(a1[j] <= a2[i] && j <= c1) {
if(a1[j] == a2[i]) cnt[i] ;
j ;
}
}
/*
for(int i = 1; i <= c1; i )
for(int j = 1; j <= c2; j )
ans = (a1[i] == a2[j]);
*/
for(int i = 1; i <= c2; i ) ans = cnt[i];
cout << ans;
return 0;
}
