题目(材料题)
|
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 } |
关注我们
