题目(材料题)
01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #include <vector>
05 #define ll long long
06 int n, m;
07 std::vector<int> k, p;
08 inline int mpow(int x, int k) {
09 int ans = 1;
10 for (; k; k = k >> 1, x = x * x) {
11 if (k & 1)
12 ans = ans * x;
13 }
14 return ans;
15 }
16 std::vector<int> ans1, ans2;
17 int cnt1, cnt2;
18 inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19 if (l > r) {
20 ++cnt;
21 ans.push_back(v);
22 return;
23 }
24 for (int i = 1; i <= m; ++i) {
25 dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26 }
27 return;
28 }
29 std::vector<int> cntans1;
30 int main() {
31 scanf("%d%d", &n, &m);
32 k.resize(n + 1);
33 p.resize(n + 1);
34 for (int i = 1; i <= n; ++i) {
35 scanf("%d%d", &k[i], &p[i]);
36 }
37 dfs(ans1, cnt1, 1, n >> 1, 0);
38 dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39 std::sort(ans1.begin(), ans1.end());
40 int newcnt1 = 1;
41 cntans1.push_back(1);
42 for (int i = 1; i < cnt1; ++i) {
43 if (ans1[i] == ans1[newcnt1 - 1]) {
44 ++cntans1[newcnt1 - 1];
45 } else {
46 ans1[newcnt1++] = ans1[i];
47 cntans1.push_back(1);
48 }
49 }
50 cnt1 = newcnt1;
51 std::sort(ans2.begin(), ans2.end());
52 int las = 0;
53 ll ans = 0;
54 for (int i = cnt2 - 1; i >= 0; --i) {
55 for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56 ;
57 if (las < cnt1 && ans1[las] + ans2[i] == 0)
58 ans += cntans1[las];
59 }
60 printf("%lld\n", ans);
61 return 0;
62 }
关注我们
