思路
容易发现,题目要求我们动态维护这样一个多项式。
\[\prod_{i}(1-p_i+p_ix) \]如何维护。
由于精度问题,我们很难去进行一个多项式除法将其暴力求出。
考虑 \(p_i\le 0.2\)。
可以得知,我们的多项式的数的增减是比较大的。
那么在一定数量后,一些可能有值的系数在当前精度下是可以认为是零的。
这样就对多项式长度有了保障。
我们可以将所有询问丢到线段树上。
暴力维护两个多项式。
在多项式乘法的时候。
我们仅维护有值的位置。
就可以以较快的速度通过此题。
复杂度不会算。
Code
#include <bits/stdc++.h>
using namespace std;
int m, n, t, q, ln[1010];
double a[510];
double b[510];
set<pair<int, int>> v[1010];
struct Poly {
int l, r;
double f[300000]{};
Poly() { l = 0, r = 0, f[0] = 1; }
inline void add(int x, int y) {
double p = a[x] + b[y];
double q = 1 - p;
r++;
for (int i = r; i >= l; i--) {
f[i] = f[i] * q;
if (i != l) f[i] += f[i - 1] * p;
}
while (l < r && f[l] < 1e-12) l++;
while (l < r && f[r] < 1e-12) r--;
}
};
Poly cur;
inline void build(int p, int l, int r) {
if (l == r) {
cin >> ln[p];
for (int i = 1; i <= ln[p]; i++) {
int x, y;
cin >> x >> y, v[p].emplace(x, y);
}
} else {
int mid = (l + r) >> 1;
build(mid<<1, l, mid);
build(mid<<1|1, mid + 1, r);
for (auto i : v[mid<<1]) v[p].insert(i);
for (auto i : v[mid<<1|1]) v[p].insert(i);
}
}
inline void solve(int p, int l, int r) {
if (l == r) {
Poly res;
for (auto i : v[p])
res.add(i.first, i.second);
double pos = 0;
for (int i = 0; i <= ln[p]; i++) {
if (t - i >= 0) pos += res.f[i] * cur.f[t - i];
}
for (int i = 0; i <= ln[p]; i++) {
if (t - i >= 0) printf("%.9lf ", res.f[i] * cur.f[t - i] / pos); else printf("0 ");
}
printf("\n");
} else {
int mid = (l + r) >> 1;
Poly back = cur;
for (auto i : v[p]) if (!v[mid<<1].count(i)) cur.add(i.first, i.second);
solve(mid<<1, l, mid);
cur = back;
for (auto i : v[p]) if (!v[mid<<1|1].count(i)) cur.add(i.first, i.second);
solve(mid<<1|1, mid + 1, r);
cur = back;
}
}
int main() {
cin >> m >> n >> t >> q;
if (!q) return 0;
for (int i = 1; i <= m; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
build(1, 1, q);
for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (!v[1].count({i, j})) cur.add(i, j);
solve(1, 1, q);
}
标签:WF,ICPC2020,cur,int,题解,mid,Poly,double,多项式
From: https://www.cnblogs.com/JiaY19/p/18400231