概率期望DP做题记录-Part3

P3750 [六省联考 2017] 分手是祝愿

~~什么题目名称~~

题意

给定 \(n\) 个灯的初始状态，每个灯有两个状态亮和灭，通过操作第 \(i\) 个开关，所有编号为 \(i\) 的约数（包括 \(1\) 和 \(i\)）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

你的目标是使所有灯都灭掉。

每次你会等概率随机操作一个开关，直到所有灯都灭掉。

B 君想知道按照这个策略（也就是先随机操作，最后最小操作次数小于等于 \(k\) 步时，再使用操作次数最小的操作方法）的操作次数的期望。

求这个期望乘以 \(n\) 的阶乘对 \(100003\) 取模之后的结果。\(n\le 10^5\)。

做法

先考虑已知这些路灯的亮灭状态，如何求出最小操作次数。

不难发现，从 \(n\) 到 \(1\)，有亮的就把它按掉，一定是最优的。

不妨假设当前位置为 \(i\)。

当 \(i=n\) 时，只能把 \(i\) 按灭掉。
当 \(1\le i\le n\) 时，假设 \([i+1,n]\) 都灭了。首先，更小的不能让 \(i\) 灭掉。如果试图用更大的把 \(i\) 按掉，那么就会一直需要更大的把按亮的按回去，直到没有更大的能把它按回去，这时候还是要一个一个按回去，不如直接把 \(i\) 按掉。

这样感性理解，就说明了从大到小按掉是最优的做法之一。

对于一个序列，根据刚才的过程，容易发现，需要按一下的点是固定的。因为这个操作是异或，所以顺序没有影响。

现在问题就转化成了，给定一个 \(01\) 串，每次随机选定一个位置异或 \(1\)，问变成全 \(0\) 的期望步数。

然后就好做了。容易发现期望步数只与 \(1\) 的个数有关，而且最小操作次数等于 \(1\) 的数量。

不妨设 \(dp_i\) 表示从有 \(i\) 个 \(1\) 变成 \(i-1\) 个 \(1\) 的期望步数。

显然转移为：

\[\begin{align} dp_i&=\frac{i}{n}+\frac{n-i}{n}(dp_i+dp_{i+1}+1)\nonumber\\ dp_i&=\frac{i}{n}+\frac{n-i}{n}dp_i+\frac{n-i}{n}dp_{i+1}+\frac{n-i}{n}\nonumber\\ dp_i&=1+\frac{n-i}{n}dp_i+\frac{n-i}{n}dp_{i+1}\nonumber\\ dp_i-\frac{n-i}{n}dp_i&=1+\frac{n-i}{n}dp_{i+1}\nonumber\\ \frac{i}{n}dp_i&=1+\frac{n-i}{n}dp_{i+1}\nonumber\\ dp_i&=1+\frac{n+(n-i)dp_{i+1}}{i}\nonumber\\ \end{align} \]

直接转移即可。

那么步数的期望就是 \(E=\sum_{i=k+1}^{count}dp_i+k\)。\(count\) 表示初始 \(1\) 的数量。

直接计算即可，记得要乘上 \(n!\)。

代码

void update(int x){
	for(int i=1;i*i<=x;i++){
		if(x%i)continue;
		a[i]^=1;
		if(i*i!=x)a[x/i]^=1;
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=n;i;i--){
		if(a[i]){
			update(i);
			++cnt;
		}
	}
	m=min(cnt,m);
	for(int i=n;i;i--)dp[i]=(n+(n-i)*dp[i+1])%mod*inv(i)%mod;
	for(int i=m+1;i<=cnt;i++)ans=(ans+dp[i])%mod;
	ans+=m;
	for(int i=1;i<=n;i++)ans=ans*i%mod;
	cout<<ans;
	return 0;
}