2020-2021:teams:farmer_john:2020hdu暑期多校第七场

差别

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

到此差别页面的链接

--- 2020-2021:teams:farmer_john:2020hdu暑期多校第七场 [2020/08/21 16:45]
jjleo [题意]
+++ 2020-2021:teams:farmer_john:2020hdu暑期多校第七场 [2020/10/07 21:31] (当前版本)
jjleo ↷ 页面名由2020-2021:teams:farmer_john:2020_multi-university_training_contest_7改为2020-2021:teams:farmer_john:2020hdu暑期多校第七场
@@ 行 1: / 行 1: @@
-======比赛名称======
+======2020HDU暑期多校第七场======
 [[https://vjudge.net/contest/390235|比赛链接]]
 =====A.=====
@@ 行 21: / 行 21: @@
 **solved by JJLeo**
 ====题意====
-给定$t,a,c,m$，
+给定$t,a,c,m$，等概率地从$[0,t]$中选择两个数$v_1,v_2$，设$X_0=v_1+v_2$，$X_{n+1}=(aX_n+c) \mod m (n \ge 0)$，求$X_{|v_1-v_2|}$是偶数的期望，输出最简分数。$(2 \leq m \leq 10^6, 0 \leq a, c < m, 0 \leq t < \frac{m}{2})$
 ====题解====
+可以发现$X$数组本质上是多个环，因此我们可以考虑当$v_1+v_2=b$时，$|v_1-v_2|$的取值情况，分奇偶以及$v_1+v_2$与$t$的大小关系讨论一下可以发现本质上就是求环上某个点往后两个两个跳，遇到的所有点其中点上数字是偶数的数量，倍增处理一下即可，本题难点在上述讨论过程中细节上的一些处理。
 =====E.=====
 **upsolved by JJLeo**
 ====题意====
+数轴上一共有$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)$。
 =====F.=====
 **upsolved by **

2020-2021/teams/farmer_john/2020hdu暑期多校第七场.1597999500.txt.gz · 最后更改: 2020/08/21 16:45 由 jjleo