[BZOJ4872/Luogu3750][Shoi2017]分手是祝愿(期望动态规划,逆元)

发布于 2018-02-06  131 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4872/Luogu3750][Shoi2017]分手是祝愿(期望动态规划,逆元)

Description

Zeit und Raum trennen dich und mich.
时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n 个开关组成,给定这 n 个灯的初始状态,下标为从 1 到 n 的正整数。每个灯有两个状态亮和灭,我们用 1 来表示这个灯是亮的,用 0 表示这个灯是灭的,游戏的目标是使所有灯都灭掉。但是当操作第 i 个开关时,所有编号为 i 的约数(包括 1 和 i)的灯的状态都会被改变,即从亮变成灭,或者是从灭变成亮。B 君发现这个游戏很难,于是想到了这样的一个策略,每次等概率随机操作一个开关,直到所有灯都灭掉。这个策略需要的操作次数很多, B 君想到这样的一个优化。如果当前局面,可以通过操作小于等于 k 个开关使所有灯都灭掉,那么他将不再随机,直接选择操作次数最小的操作方法(这个策略显然小于等于 k 步)操作这些开关。B 君想知道按照这个策略(也就是先随机操作,最后小于等于 k 步,使用操作次数最小的操作方法)的操作次数的期望。这个期望可能很大,但是 B 君发现这个期望乘以 n 的阶乘一定是整数,所以他只需要知道这个整数对 100003 取模之后的结果。

Http

BZOJ
Luogu

Tag

期望动态规划,逆元

解决思路

首先考虑如何得到最少步数,由于更改一个灯的状态只会影响到比它小的灯,所以我们可以从大往小依次把灯的状态更改,\(O\sqrt{n}\)地枚举约数修改。可以证明其它的方法不会更优。
那么这样我们就知道有那些灯是一定会被关的,由于一盏灯被关多次是没有用的,所以这些应该被关掉的灯的顺序是与答案没有关系的。实际上,这些被关掉的灯的位置也是与计数无关的,我们只要知道需要关掉多少盏灯即可,因为最后的答案只与它有关。
那么问题转化为求在\(n\)个物品中,我们要选择确定的\(tot\)个(即要关掉的灯数),多选的其它物品可以花费一个回合丢掉(为什么是回合,没错我文明玩多了)。选择是随机的,每一次等概率选择一个物品或丢掉一个物品,而当剩下要求选的物品小于等于\(K\)时,直接选择这些物品。求期望步数。
那么首先有一个简单的想法,就是设\(F[i]\)表示还剩\(i\)个必选的物品没选的期望,则\(F[i]\)可以由\(F[i+1],F[i-1]\)分别转移过来,即\(F[i]=\frac{i}{n}F[i+1]+\frac{n-i}{n}F[i+1]\),但这样不好解,需要通过\(F[n]=F[n-1]+1\),一个一个方程地化。
我们换一个思路,考虑设\(f[i]\)表示从剩下了\(i\)个正确的物品没选到剩下了\(i-1\)个正确的物品没选的期望步数,那么首先对于小于等于\(K\)的\(i\),有\(f[i]=1\),\(f[n]\)也是\(1\),因为\(n\)只能向\(n-1\)转移。
剩下的怎么转移呢?
考虑原来之前我们定义的\(F\),其实就是\(f\)的前缀和,那么我们试着由前缀和的式子反推一下?
\[F[i]=\sum_{j=1}^{i}=\frac{i}{n} \sum_{j=1}^{i-1} f[j]+\frac{n-i}{n} \sum_{j=1}^{i+1} f[j]+1\]
发现有很多可以抵掉的,化简后得
\[f[i]=\frac{i}{n}+\frac{n-i}{n}(f[i+1]+f[i]+1)\]
这样就只有两个变量了,移项得到
\[f[i]=\frac{n+(n-i)f[i+1]}{i}\]
这样就可以从后往前递推了,因为有除以\(i\),所以可以提前递推求出逆元。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4872/Luogu3750][Shoi2017]分手是祝愿(期望动态规划,逆元)


HNCJ OIer