思路：
记：
s
u
m
=
∑
i
=
1
n
p
i
∗
m
i
sum = \sum_{i=1}^{n}p_i*m_i
sum=i=1∑npi∗mi 构造母函数：
Π
i
=
1
n
(
∑
j
=
0
m
i
(
p
i
∗
x
j
∗
p
i
)
)
\Pi_{i=1}^{n}(\sum_{j=0}^{m_i}(p_i*x^{j*p_i}))
Πi=1n(j=0∑mi(pi∗xj∗pi)) 展开之后，关于
x
x
x的多项式：
a
0
+
a
1
∗
x
+
a
2
∗
x
2
+
.
.
.
+
a
s
u
m
∗
x
s
u
m
a_0+a_1*x+a_2*x^2+...+a_{sum}*x^{sum}
a0+a1∗x+a2∗x2+...+asum∗xsum，其中的项
x
s
u
m
/
3
x^{sum/3}
xsum/3的系数对
M
O
D
MOD
MOD取模，即为答案。
注：封装多项式类，class不是很熟悉写的很慢。
代码：
#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
;
}
}
}
}
