思路:
记:
sum=i=1∑npi∗mi
构造母函数:
Πi=1n(j=0∑mi(pi∗xj∗pi))
展开之后,关于 x的多项式: a0+a1∗x+a2∗x2+...+asum∗xsum,其中的项 xsum/3的系数对 MOD取模,即为答案。
注:封装多项式类,class不是很熟悉写的很慢。
代码:
// HDU - 2110.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Polynomial
{
private:
vector<std::pair<int, int>> x;
public:
Polynomial();
Polynomial(int p, int m);
Polynomial operator * (const Polynomial& r) const;
void print() const;
int query_first(int val);
};
Polynomial::Polynomial() {
x.clear();
}
Polynomial::Polynomial(int p, int m) {
x.clear();
for (int i = 0; i <= m; i++) {
x.push_back(make_pair(1, i * p));
}
}
bool pair_cmp(const pair<int, int>& l, const pair<int, int>& r) {
return l.second < r.second;
}
Polynomial Polynomial::operator * ( const Polynomial &other) const {
Polynomial temp, ret;
for (int i = 0; i < (int)this->x.size(); i++) {
for (int j = 0; j < (int)other.x.size(); j++) {
temp.x.push_back(make_pair(this->x[i].first * other.x[j].first, this->x[i].second + other.x[j].second));
}
}
sort(temp.x.begin(), temp.x.end(), pair_cmp);
for (int i = 0; i < (int)temp.x.size(); i++) {
if (i == 0 || ret.x[ret.x.size() - 1].second != temp.x[i].second) {
ret.x.push_back(make_pair(temp.x[i].first, temp.x[i].second));
}
else {
ret.x[ret.x.size() - 1].first += temp.x[i].first;
}
}
for (int i = 0; i < (int)ret.x.size(); i++) {
ret.x[i].first = ret.x[i].first % 10000;
}
return ret;
}
void Polynomial::print()const {
for (int i = 0; i < (int)this->x.size(); i++) {
if (i != 0) {
cout << " + ";
}
cout << x[i].first << "*X^" << x[i].second;
}
cout << endl;
}
int Polynomial::query_first(int val) {
for (int i = 0; i < (int)this->x.size(); i++) {
if (this->x[i].second == val) {
return this->x[i].first;
}
}
return -1;
}
int main()
{
int n;
while (cin >> n) {
if (n == 0)break;
Polynomial ans = Polynomial(1, 0), temp;
int sum = 0;
for (int i = 0; i < n; i++) {
int val, num;
cin >> val >> num;
ans = ans * Polynomial(val, num);
sum += num * val;
}
if (sum % 3 != 0) {
cout << "sorry" << endl;
}
else {
int m = ans.query_first(sum / 3);
if (m == -1) {
cout << "sorry" << endl;
}
else {
cout << m << endl;
}
}
}
}