2020-2021:teams:farmer_john:2020hdu暑期多校第七场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020hdu暑期多校第七场 [2020/08/21 16:38] 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|比赛链接]] | [[https://vjudge.net/contest/390235|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 19: | 行 19: | ||
| ====题解==== | ====题解==== | ||
| =====D.===== | =====D.===== | ||
| - | **upsolved by ** | + | **solved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 给定$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.===== | =====E.===== | ||
| - | **upsolved by** | + | **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.===== | =====F.===== | ||
| **upsolved by ** | **upsolved by ** | ||
| 行 39: | 行 49: | ||
| =====H.===== | =====H.===== | ||
| - | **upsolved by ** | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| 行 55: | 行 65: | ||
| 定义所有横纵坐标不互质的点为“好点”，现在初始在一个好点上，每次可以不动或者前往周围八个格子中的好点，上述操作均等概率随机，设走$p_t$为游走$t$次后回到初始点的概率，求$\lim \limits_{t \to +\infty} p_t$。 | 定义所有横纵坐标不互质的点为“好点”，现在初始在一个好点上，每次可以不动或者前往周围八个格子中的好点，上述操作均等概率随机，设走$p_t$为游走$t$次后回到初始点的概率，求$\lim \limits_{t \to +\infty} p_t$。 | ||
| ====题解==== | ====题解==== | ||
| - | 如果能走到对角线答案为$0$，否则盲猜个数不会很多，因此直接爆搜，再观察样例盲猜出答案为“起点可移动的方向（包括不动）”除以“所有点可移动的方向（包括不动）之和”。\\ | + | 如果能走到对角线答案为$0$，否则盲猜好点的个数不会很多，因此直接爆搜，再观察样例盲猜出答案为“起点可移动的方向（包括不动）”除以“所有点可移动的方向（包括不动）之和”。\\ |
| 而这样做的正确性，题解如是说：至于证明极限的存在性，需要涉及关于邻接矩阵的特征值等内容，可以自行查阅“图上随机游走”相关书籍文献。 | 而这样做的正确性，题解如是说：至于证明极限的存在性，需要涉及关于邻接矩阵的特征值等内容，可以自行查阅“图上随机游走”相关书籍文献。 | ||
| =====记录===== | =====记录===== | ||
| 行 71: | 行 81: | ||
| =====总结===== | =====总结===== | ||
| * MJX：考试前一天早点睡，以免太困 | * MJX：考试前一天早点睡，以免太困 | ||
| + | * ZYF：啥也不会，我学还不行吗。（但为什么某卷翻天的题会无限TLE） | ||
2020-2021/teams/farmer_john/2020hdu暑期多校第七场.1597999084.txt.gz · 最后更改: 2020/08/21 16:38 由 jjleo
