将所有多项式存入Poly中
求导就是 对应项的系数 乘以 阶数,然后阶数减一
先把所有多项式存下来,然后对于每一次询问求导出对应的多项式
然后再带入对应的变量数组即可
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int mod = 1e9 + 7;
int n, m;
ll qmi(ll x, ll n) {
ll ans = 1;
while (n) {
if (n & 1) {
ans = ans * x % mod;
}
x = (x * x) % mod;
n >>= 1;
}
return (ans % mod + mod) % mod;
}
struct Poly {
vector<vector<ll>> f;
Poly() : f{} {}
Poly(ll d, int flag) {
vector<ll> t(n + 1, 0);
t[0] = 1;
if (flag == 1) {
// x1
t[d] = 1;
} else {
//常数
t[0] = d;
}
f.push_back(t);
}
};
void calc(Poly &a, Poly &b, string &op);
ll findAns(Poly &a, vector<ll> &t);
stack<Poly> st;
int main() {
cin >> n >> m;
string str;
getline(cin, str);
getline(cin, str);
stringstream oss(str);
while (oss >> str) {
if (str == "+" || str == "-" || str == "*") {
Poly a = st.top();
st.pop();
Poly b = st.top();
st.pop();
calc(a, b, str);
} else if (str[0] == 'x') {
ll ind = stoi(str.substr(1));
Poly t(ind, 1);
st.push(t);
} else { //
ll x = stoi(str);
Poly t(x, 2);
st.push(t);
}
}
Poly a = st.top();
while (m--) {
ll ind;
vector<ll> in;
cin >> ind;
in.push_back(ind);
for (int i = 0; i < n; i++) {
ll x;
cin >> x;
in.push_back(x);
}
cout << findAns(a, in) << endl;
}
}
void calc(Poly &a, Poly &b, string &op) {
Poly res;
if (op == "+") {
for (auto &x : a.f) {
res.f.push_back(x);
}
for (auto &x : b.f) {
res.f.push_back(x);
}
} else if (op == "-") {
for (auto &x : a.f) {
res.f.push_back(x);
}
for (auto &x : res.f) {
x[0] = -1 * x[0];
}
for (auto &x : b.f) {
res.f.push_back(x);
}
} else {
for (auto &x : a.f) {
for (auto &y : b.f) {
vector<ll> temp(n + 1, 0);
temp[0] = x[0] * y[0];
for (int i = 1; i <= n; i++) {
temp[i] = x[i] + y[i];
}
res.f.push_back(temp);
}
}
}
st.push(res);
}
ll findAns(Poly &a, vector<ll> &t) {
Poly tt;
for (auto x : a.f) tt.f.push_back(x);
ll ind = t[0];
for (auto &x : tt.f) {
if (!x[ind])
x[0] = 0;
else {
x[0] = (x[0] * x[ind]) % mod;
x[ind]--;
}
}
ll sum = 0;
for (auto &x : tt.f) {
ll temp = x[0];
if (!temp) continue;
for (int i = 1; i <= n; i++) {
temp = (temp * qmi(t[i], x[i])) % mod;
}
sum += temp;
sum %= mod;
}
return ((sum % mod) + mod) % mod;
}
太牛了啊多项式都会