A22458. #include <algorithm> #include <stdio> #include <crlmp> #include <vector> #define ll long long int n, m; std::vector<int> k, p; inline int mpow(int x, int k) { int ans = 1; for (; k; k = k >> 1, x = x…

#include <algorithm>
#include <stdio>
#include <crlmp>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;

inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k = k >> 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}

std::vector<int> ans1, ans2;
int cnt1, cnt2;

inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}

std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &k[i], &p[i]);
}
dfs(ans1, cnt1, 1, n >> 1, 0);
dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
std::sort(ans1.begin(), ans1.end());
int newcnt1 = 1;
cntans1.push_back(1);
for (int i = 1; i < cnt1; ++i) {
    if (ans1[i] == ans1[newcnt1 - 1]) {
        ++cntans1[newcnt1 - 1];
    } else {
        ans1[newcnt1++] = ans1[i];
        cntans1.push_back(1);
    }
}
cnt1 = newcnt1;
std::sort(ans2.begin(), ans2.end());
int las = 0;
ll ans = 0;
for (int i = cnt2 - 1; i >= 0; --i) {
    for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
        ;
    if (las < cnt1 && ans1[las] + ans2[i] == 0)
        ans += cntans1[las];
}
printf("%lld\n", ans);
return 0;
}

删除第 51 行的“std::sort(ans2.begin(), ans2.end(),”后，代码输出的结果不会受到影响。（    ）