2020-2021:teams:farmer_john:2020hdu暑期多校第七场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020hdu暑期多校第七场 [2020/08/21 17:02] 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.===== | ||
| 行 27: | 行 27: | ||
| **upsolved by JJLeo** | **upsolved by JJLeo** | ||
| ====题意==== | ====题意==== | ||
| - | 数轴上一共有$2n+1$个点，每个点的坐标为$x_i$，下标为奇数的点为洞，下标为偶数的点为球，每次等概率地随机选择一个球，等概率地往左或往右推动它，直到它落入遇到的第一个洞里，每个洞只能放一个球。求球滚过距离之和的期望，对$998244353$取模，多组询问。$(n \le 3000, \sum n \le 10^6)$ | + | 数轴上一共有$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 ** | ||
2020-2021/teams/farmer_john/2020hdu暑期多校第七场.1598000525.txt.gz · 最后更改: 2020/08/21 17:02 由 jjleo
