AI题库 · 信息学奥赛-提高级题库
题目分享 #22033
include <algorithm>
include <cstdio>
include <cstring>
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) {
while (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;
}
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。