等比数列算概率, 然后按顺序插, 在树状数组里查一下.
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #include <cmath>
- #include <set>
- #include <cctype>
- using std::min;
- using std::max;
- using std::swap;
- using std::memset;
- using std::vector;
- using std::set;
- using std::isdigit;
- using std::pow;
- const int maxn = 5e+5 + 5;
- int n, m;
- long double p;
- set<int> tb[maxn];
- long double ans, b[maxn];
- void add(int x, long double c) {for(; x <= n; x += (x & -x)) b[x] += c;}
- long double sum(int x) {long double ret = 0.0; for(; x; x -= (x & -x)) ret += b[x]; return ret;}
- inline int rd()
- {
- int x = 0; char c = getchar();
- while(!isdigit(c)) c = getchar();
- while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
- return x;
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- scanf("%Lf", &p);
- for(register int i = 1; i <= m; ++i)
- {
- int a = rd(), b = rd();
- tb[a].insert(b);
- }
- for(register int i = 1; i <= n; ++i)
- {
- int tot = 0, siz = tb[i].size();
- for(set<int>::iterator it = tb[i].begin(); it != tb[i].end(); ++it)
- {
- //ans += sum(m) - sum(*it);
- double ppm = p * pow(1 - p, tot) / (1.0 - pow(1 - p, siz));
- ans += ppm * (sum(m) - sum(*it));
- add(*it, ppm);
- tot++;
- }
- }
- printf("%.2Lf\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2763134.html