2020-2021:teams:farmer_john:week_16

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:farmer_john:week_16 [2020/08/21 16:34]
bazoka13
+++ 2020-2021:teams:farmer_john:week_16 [2020/10/16 06:27] (当前版本)
40.77.167.195 ↷ 链接因页面移动而自动修正
@@ 行 1: / 行 1: @@
 =====团队训练=====
 ^ 比赛时间 ^ 比赛名称 ^ 当场过题数 ^ 至今过题数 ^ 总题数 ^ 排名 ^
-|2020-08-20| [[2020 Multi-University Training Contest 7|HDU 2020 Multi-University Training Contest 7]] |  4  |  5  |  11  |28/757|
+|2020-08-20| [[2020hdu暑期多校第七场|HDU 2020 Multi-University Training Contest 7]] |  4  |  6  |  11  |28/757|
 ===== 本周推荐 =====
@@ 行 23: / 行 23: @@
   * comment：学弟出的题真的🐂啊，，，
 ====JJLeo===
-===题目名称===
+===2020HDU多校第七场E Expectation==
-  * 分类：
+  * 分类：动态规划，概率期望。
-  * 题意：
+  * 题意：数轴上一共有$2n+1$个点，每个点的坐标为$x_i$，下标为奇数的点为洞，下标为偶数的点为球，每次等概率地随机选择一个球，等概率地往左或往右推动它，直到它落入遇到的第一个洞里，每个洞只能放一个球。求球滚过距离之和的期望，对$998244353$取模，多组数据。$(n \le 3000, \sum n \le 10^6)$
-  * 题解：
+  * 题解：每次推球这个过程可以转化为从一个序列中每次选择两个相邻的数，使得总路程增加$|x_i-x_j|$，然后将这两个数从序列中删除，不断重复上述操作直到只剩下一个数。考虑拆开上述的绝对值，一个数如果和它右边的数一起被删，贡献为$-x_i$；如果和它左边的数一起被删，贡献为$x_i$；如果没被删，贡献为$0$。因此我们设$f_{i,j}$为一个数左边有$i$个数，右边有$j$个数时和它右边的数一起被删的概率，我们可以通过$O(n^2)$dp预处理出该数组，考虑当前状态一共有$(i+j)$种删除方案，对于每一种删除后都可以转化为一个子问题，因此有如下的递推：<code cpp>for(int i = 0;i <= n;i++){
+	for(int j = 1;i + j <= n;j++){
+		if((i + j) & 1) continue;//显然本题中i+j必然为偶数
+		if(j) f[i][j] = 1;
+		if(j > 1) f[i][j] = (f[i][j] + 1ll * f[i][j - 2] * (j - 1)) % p;
+		if(i > 1) f[i][j] = (f[i][j] + 1ll * f[i - 2][j] * (i - 1)) % p;
+		f[i][j] = 1ll * f[i][j] * inv[i + j] % p;
+	}
+}</code>最后对于每一组数据，答案为$\sum_{i=1}^{2n+1}(f_{n-i,i-1}x_i-f_{i-1,n-i}x_i)$，总复杂度$O(n^2+\sum n)$。
-  * comment：
+  * comment：转化过于巧妙，同时$n$奇特的范围也在暗示预处理。
 =====个人训练=====
 ===== 2sozx =====
@@ 行 45: / 行 53: @@
 ==== 题目 ====
+  * [[.jjleo:暑假题目汇总]]

2020-2021/teams/farmer_john/week_16.1597998863.txt.gz · 最后更改: 2020/08/21 16:34 由 bazoka13