网站开发 自动填写表单,汕头市网站建设分站服务机构,网站建设的结论和体会,如何建立网站管理系统选书问题
金牌导航 期望-7
题目大意
有n个人#xff0c;每个人有自己的选书目录#xff0c;一个人有p的概率选当前的书#xff0c;有1-p的概率不选#xff0c;即去查看下一本书#xff08;过n后回到1#xff09;#xff0c;现在问你选书的逆序对的期望数
输入样例
…选书问题
金牌导航 期望-7
题目大意
有n个人每个人有自己的选书目录一个人有p的概率选当前的书有1-p的概率不选即去查看下一本书过n后回到1现在问你选书的逆序对的期望数
输入样例
5 5
0.5
5 1
3 2
2 2
2 1
3 1输出样例
0.89数据范围
1⩽N,M⩽5×105,0.4⩽p⩽0.61\leqslant N,M\leqslant 5\times 10^5,0.4\leqslant p \leqslant 0.61⩽N,M⩽5×105,0.4⩽p⩽0.6
解题思路
对于1个人设f_i为选第i本书的期望值num_i为选书目录里里书的数量 那么有: f2f1p×(1−p)×pf1×(1−p)f_2\frac{f_1}{p}\times (1-p)\times p f_1\times (1-p)f2pf1×(1−p)×pf1×(1−p) f1p\frac{f_1}{p}pf1为查看f1f_1f1的期望值1-p是第一本书不选p为选第二本书 同理则有 f3f2p×(1−p)×pf2×(1−p)f1×(1−p)2f4f3p×(1−p)×pf3×(1−p)f1×(1−p)3...fnumifnumi−1p×(1−p)×pfnumi−1×(1−p)f1×(1−p)numi−1f_3\frac{f_2}{p}\times (1-p)\times p f_2\times (1-p) f_1\times (1-p)^2\\ f_4\frac{f_3}{p}\times (1-p)\times p f_3\times (1-p) f_1\times (1-p)^3\\ ...\\ f_{num_i}\frac{f_{num_i - 1}}{p}\times (1-p)\times p f_{num_i-1}\times (1-p) f_1\times (1-p)^{num_i-1}f3pf2×(1−p)×pf2×(1−p)f1×(1−p)2f4pf3×(1−p)×pf3×(1−p)f1×(1−p)3...fnumipfnumi−1×(1−p)×pfnumi−1×(1−p)f1×(1−p)numi−1 那么有p为最初始的一次 f1fnumip×(1−p)×pfnumi×(1−p)f1×(1−p)numipf_1\frac{f_{num_i}}{p}\times (1-p)\times p f_{num_i}\times (1-p) f_1\times (1-p)^{num_i}pf1pfnumi×(1−p)×pfnumi×(1−p)f1×(1−p)numip 解该方程 f1f1×(1−p)numipf1×(1−(1−p)numi)pf1p1−(1−p)numi\begin{aligned}f_1 f_1\times (1-p)^{num_i}p \\ f_1\times(1-(1-p)^{num_i}) p\\f_1\frac{p}{1-(1-p)^{num_i}}\end{aligned}f1f1×(1−(1−p)numi)f1f1×(1−p)numipp1−(1−p)numip 得到f后利用树状数组求逆序对即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 500010
using namespace std;
int n, m, w, s[N], num[N], first[N], last[N], next[N];
double p, g, ans, c[N], pw[N], sum;
struct node
{int x, y;
}a[N];
double ask(int x)//树状数组
{double sum 0;for (; x; x - x-x)sum c[x];return sum;
}
void add(int x, double y)
{for (; x 500000; x x-x)c[x] y;return;
}
bool cmp(node x, node y)
{return x.x y.x || x.x y.x x.y y.y;//按编号排序
}
int main()
{scanf(%d%d%lf, n, m, p);for (int i 1; i m; i){scanf(%d%d, a[i].x, a[i].y);num[a[i].x];}sort(a 1, a 1 m, cmp);pw[0] 1;for (int i 1; i n; i)pw[i] pw[i - 1] * (1 - p);for (int i 1; i m; i){if (a[i].x ! a[i - 1].x) g p / (1.0 - pw[num[a[i].x]]);//新的一个数的期望else g g * (1 - p);//不是新的就乘1-p来求ans (sum - ask(a[i].y)) * g;//前面加入的人的编号都比当前小只要找到书的编号大的即可add(a[i].y, g);sum g;}printf(%.2lf, ans);return 0;
}
